코드

from collections import Counter
class Solution:
    def minSetSize(self, arr: [int]) -> int:
        count_list = Counter(arr).most_common()
        total = 0
        count = 0

        for _, list_count in count_list:
            total += list_count
            count += 1

            if total >= len(arr) // 2:
                return count

풀이 과정

사용한 횟수 들을 배열로 묶은 뒤 가장 많이 사용한 횟수를 더하면서 arr 의 절반 크기와 같거나 크다면 count 값은 반환하는 걸로 하였다.

Counter 모듈을 이용하여 배열의 갯수들을 묶어준 counter 객체를 만들고 이후 most_common 을 활용하여 많이 사용한 순서대로 정리를 하였습니다.

이후 정리된 count_list 의 아이템에만 접근을 해서 total 에 값을 더해주고 만약 total 의 값이 len(arr)//2 를 벗어난 경우 = 조건 충족

반복된 함수의 길이인 count 를 반환합니다.

이번 문제의 경우 heap 을 이용하라고 하였지만 문제를 봤을 때 힙이 필요한 위치는 보이지 않았습니다.

힙 사용해야 한다면 다음과 같이 사용할 수는 있을 것 같다.

import heapq
from collections import Counter

class Solution:
    def minSetSize(self, arr: [int]) -> int:
        count_list = Counter(arr)
        max_heap = [-freq for freq in count_list.values()]
        heapq.heapify(max_heap)
        
        total = 0
        count = 0

        while total < len(arr) // 2:
            total += -heapq.heappop(max_heap)
            count += 1

        return count

하지만 Counter 에서는 most_common() 이라는 메소드를 제공하기 때문에 굳이 사용하지 않았다. 실제로 차이는 얼마 나지 않았다.

most_common()을 사용한 경우

heap을 사용한 경우