[코테] 99클럽 코테 스터디 39일차 TIL - 힙

Question1 - [미들러] 열 크기를 반으로 줄이기 (Reduce Array Size to The Half)

 

You are given an integer array arr. You can choose a set of integers and remove all the occurrences of these integers in the array.

Return the minimum size of the set so that at least half of the integers of the array are removed.

 

Example 1:

• Input: arr = [3,3,3,3,5,5,5,2,2,7]
• Output: 2
• Explanation: Choosing {3,7} will make the new array [5,5,5,2,2] which has size 5 (i.e equal to half of the size of the old array).
• Possible sets of size 2 are {3,5},{3,2},{5,2}.
• Choosing set {2,7} is not possible as it will make the new array [3,3,3,3,5,5,5] which has a size greater than half of the size of the old array.

Constraints:

• 2 <= arr.length <= 105
• arr.length is even.
• 1 <= arr[i] <= 105

---

 

문제풀이

 

힙을 이용해서, array의 사이즈를 반 이하로 줄이려고 할때, 제거해야 할 숫자의 개수의 최소값을 구해야 한다.

우선 여기에서 가장 중요한건

1) 각 숫자의 개수를 계산하는 것이다. 이를 위해 Counter 기능을 활용해서 모든 요소의 개수를 계산했다.

2) 최대힙을 활용하는 것이다. 계산된 요소의 개수들 중에서, 큰 값들부터 빼보면서 그것이 array 길이의 반보다 낮은지를 확인해야 하기 때문이다. 

 

아래의 단계에 따라서 코드를 작성했다.

• Counter를 활용, array 의 개수 카운트 결과를 count에 담고 개수 value만 count_list에 담음
• count_list를 음수화한 다음 최대힙으로 활용
• num 변수에는 개수의 누적값을 담고, num_count 변수에는 몇개의 요소를 빼야하는지를 담기위해 초기화 
• num값이 array 길이의 절반을 넘지 않는 한에서, heapq를 하나씩 빼가면서 음수화된 최대값을 누적 더함 (num), 더할 때마다 num_count 증가 (이렇게 하면 num_count를 최소값으로 유지 가능하다)
• 최종적으로 반환된 최소값의 num_count를 반환

import heapq
from collections import Counter

class Solution(object):
    def minSetSize(self, arr):
        # 길이가 절반보다 작거나 같아야 
        n = len(arr)
        # counter를 활용
        count = Counter(arr)
        count_list = count.values()
        count_list = [i*-1 for i in count_list]

        heapq.heapify(count_list) # 최대힙으로 만들기
        
        num = 0 
        num_count = 0

        while num < n // 2: 
            k = heapq.heappop(count_list)
            num -= k
            num_count += 1
        
        return num_count