문제 링크

해설

• 이 문제는 그리디로 접근해야 한다. 왜냐하면 귤의 사이즈 중에서 개수가 많은 것을 우선 순위로 선택해야 하기 때문이다.
• 귤의 사이즈별 개수를 어떻게 파악할까?
• 해시 자료구조를 이용하면 {사이즈: 개수} 형식으로 정리를 할 수 있다.
• 개수가 많은 것을 우선순위로 선택한다는 점을 이용하여 최대힙을 떠올렸다.
• 왜냐하면 최대힙은 pop을 하게 되면 항상 max값을 뽑아주기 때문이다.
• 초기 구상은 그렇게 pop을 하여 모아놓은 size 집합으로 중복을 제거하여 총 몇 종류의 size가 나올 수 있는지를 구하려고 했다.
• 그러나 size는 어차피 중복이 안 되므로 굳이 집합 자료구조를 사용하지 않고 누적차로 풀었다.

CODE

import heapq as h
from collections import defaultdict
def solution(k, tangerine):
    answer = 0
    size_cnt = defaultdict(int)
    max_heap = []
    for t in tangerine:
        size_cnt[t] += 1
    for key in size_cnt:
        h.heappush(max_heap,(-1*size_cnt[key],-1*key))
    while k > 0:
        answer += 1
        k -= -1*h.heappop(max_heap)[0]
    return answer