https://school.programmers.co.kr/learn/courses/30/lessons/138476

1. 코드

from collections import defaultdict
import heapq


def solution(k, tangerine):
    d = defaultdict(int)

    for t in tangerine:
        d[t] += 1

    h = []
    for size, qnt in sorted(d.items(), key=lambda x: (x[1], x[0])):
        heapq.heappush(h, (qnt, size))

    # 힙으로 가장 적은 개수를 가진 사이즈 를 len - k 번 뽑는다.
    for _ in range(len(tangerine) - k):
    	# ex: 사이즈가 4인 귤이 3개=(3,4)
        qnt, size = heapq.heappop(h)
        qnt -= 1  # 수량을 하나 감소시킨다.
        
        # 사이즈가 4인 귤이 2개 남았다면 힙에 다시 (2, 4)를 넣는다.
        # 해당 사이즈의 귤의 개수가 없다면 힙에 넣지 않는다.
        if qnt != 0:
            heapq.heappush(h, (qnt, size))

    return len(h)

2. 후기

1 ≤ k ≤ tangerine의 길이 ≤ 100,000를 보자마자 힙으로 접근해보면 좋겠다는 생각으로 풀었다. 다른 풀이를 보니 딕셔너리 자료형만 사용해도 풀 수 있었다.