[python3] 1338. Reduce Array Size to The Half

풀이 일자: 22.08.18

난이도: [Medium]

문제 내용

주어진 integer array를 가지고 해당 array의 length를 반 이하로 줄일 때 최소한의 빼야하는 숫자의 개수에 대한 문제였다.

arr = [3,3,3,3,5,5,5,2,2,7]

→ 이런식으로 주어졌을 때 3과 7을 뺀다면 남는 array는 [5,5,5,2,2]가 되게 되면서 기존의 1/2가 되게 된다.

 

문제 해결 흐름

1. 우선 중복되는 수를  몇 개씩 있는지 check를 해야겠다.

→ Dictionary를 이용하여 각각 몇개씩 있는지 세자.

 

2. 어떤 원소를 빼야 하는지가 아니라 최소한 빼야하는 원소의 개수에 대한 문제이니까 갯수에 대한 정보만 있으면 되겠네!

→ Dictionary의 value값만을 가져와서 list로 저장해두자

 

3. 기존 array의 1/2이하가 되도록 빼야하니까 최소한 빼야하는 개수를 알아야겠는데?

→ 기존 array의 length를 2로 나누어 올림을 해준다면 빼야하는 최소 갯수를 알 수 있겠다.

 

4. 빼야하는 최소 갯수만 넘기면 되는 거고 하나씩 뺄때마다 최대로 빼는 갯수를 check한다면 되지 않을까?

→ 각 원소의 갯수가 담긴 array를 내림차순으로 정렬해주고 앞에서부터 한개씩 더해가면서 빼야하는 최소 개수를 넘기는지만 확인하면 되겠다.

추가설명

문제의 예시를 그대로 사용한다면

arr = [3,3,3,3,5,5,5,2,2,7]

있다고 했을 때

 

1. counter = {'3':4, '5':3, '2':2, '7':1}  # arr에 있는 숫자의 개수를 그대로 센 것

2. cntList = [4, 3, 2, 1] # counter의 value값만을 저장했다.

3. minSize = len(arr) // 2 + 1 if (len(arr) / 2 - len(arr) // 2 > 0) else len(arr) // 2 # 나눈 값을 올림해주었다. math.ceil()도 무방 => 5

4. cntList = [4,3,2,1] # 내림차순해준다.

원소를 하나로 뺏을 때 가장 많이 빼는 경우가 4번 나온 3을 빼는 경우 많이 빼는 것이므로 4를 했을 때 최소한 빼야하는 개수인 5보다 작으니까 다음으로 넘어가야함

 

원소를 두개를 뺐을 때 가장 많이 빼는 경우가 4번 나온 3과 3번 나온 5를 빼는 것이므로 합치면 7이며 최소한 빼야하는 갯수인 5보다 크니까 2개가 답이다.

 

=> 원소를 최대한 많이 뺄 수 있는 경우의 수만 계산해서 최소한 빼야하는 원소의 갯수를 넘기는 그 시점이 원소를 최소한으로 빼는 경우의 수에 해당한다고 보면 된다. (Greedy식 해결법)

 

=> 관건은 Time Complexity가 O(N^2)을 만들지 않는 것으로 보인다. 

→ for와 sum을 사용시 즉,  O(N^2)을 만들게 되면 29번째의 TC에서 Time Limit Exceeded Error가 발생한다.

---

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        counter = dict()
        for i in range(len(arr)):
            if arr[i] not in counter:
                counter[arr[i]] = 0
            counter[arr[i]] += 1
        
        minSize = len(arr) // 2 + 1 if (len(arr) / 2 - len(arr) // 2 > 0) else len(arr) // 2
        cntList = list(counter.values())
        cntList.sort(reverse=True)
        
        total = 0
        for i in range(len(cntList)):
            total += cntList[i]
            if total >= minSize:
                return i + 1

다른 해결 방식

1. 내림차순 정렬을 했는데 그것보다는 priority queue를 이용한 heap을 통해 관리한다면 더 빠르지 않을까?

→ 기존에 각각의 원소의 갯수를 센 결과를 list에 넣어서 reverse 정렬을 하는 것이 아니라 heap으로 넣어서 처리해보자.

→ defualt가 max heap이기 때문에 -를 곱해줌으로써 가장 큰 수가 작게 만들어 순서가 유지되도록 하자.

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        counter = dict()
        for i in range(len(arr)):
            if arr[i] not in counter:
                counter[arr[i]] = 0
            counter[arr[i]] += 1
        
        pq = [-i for i in counter.values()]
        heapq.heapify(pq)
        
        length = len(arr)
        for i in range(len(pq)):
            result = -heapq.heappop(pq)
            length -= result   
            if length <= len(arr)/2:
                return i+1

 

문제 링크

https://leetcode.com/problems/reduce-array-size-to-the-half/