[코테] 해쉬 - 귤 고르기[프로그래머스]

문제

출처: 프로그래머스 - 귤 고르기

풀이

set 자료구조와 라이브러리 collections에서 defaultdict 혹은 Counter를 사용하면 쉽게 해결할 수 있는 해쉬 문제다.
참조 : 자주 쓰는 라이브러리

1. defaultdict 혹은 Counter를 사용하여 크기별로 갯수를 만든다.
2. 크기의 종류가 최소가 되게 반환되도록 개수가 많은 크기부터 숫자를 세어야 한다. 그래서 만든 해쉬를 크기 종류별로 개수가 많은 크기로 정렬을 한다.
3. k개 만큼 담도록 k가 0이 될때까지 k에서 크기별 개수를 차감하도록 한다. 차감할 때 set 자료구조에 크기 종류를 담아 중복이 되지 않도록 해준다.
4. k가 0이 되었다면 set 자료구조에 담긴 크기 개수를 반환하면 된다.

코드

from collections import defaultdict, Counter
def solution(k, tangerine):
    answer = set()
    
    # 1. defaultdict 사용
    dH = defaultdict(int)
    for i in tangerine:
        dH[i] += 1
    # 2. Counter 사용
    dH = Counter(tangerine)
    
    # 정렬하기 : 크기 종류별 갯수가 큰 순으로 정렬
    dH = sorted(dH.items(), key=lambda x: x[1], reverse=True)
    
    for t, n in dH: # t: 크기별 종류(type), n: 크기별 개수(number)
        if k > 0:
            k -= n
            answer.add(t)
            
    return len(answer)