귤 고르기

귤 고르기

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

문제

풀이

그리디한 방법으로 풀었다. tangerine에서 귤의 크기의 종류가 최소가 되기 위해선 해당 크기가 커야지 최소가 될 수 있다.
예를 들어서 tangerine = [1, 3, 3, 3, 5, 5]라고 하자. 우선적으로 개수가 가장 많은 3을 먼저 고르고 그 다음 5를 고르는 방법으로 해야지 귤의 종류가 최소가 될 것이다.

1. 크기별 개수를 구하기 위해서 딕셔너리를 사용하였다.
   

2. 이제 우선순위 큐(최대값)에 넣어준다.
   
   dp.keys() => 리스트 형태로 꼭 바꿔줘야함

3. 우선순위 큐에서 최대값을 k보다 클 때까지 더해준다.
   

from heapq import heappush, heappop
def solution(k, tangerine):
    q = []
    dp = {}
    
    for num in tangerine:
        if num in dp:
            dp[(num)] += 1
        else:
            dp[(num)] = 1
    
    keys = list(dp.keys())
    
    for key in keys:
        heappush(q, (-dp[key]))
    
    answer, total = 0, 0
    while True:
        total += -heappop(q)
        answer += 1
        if total >= k:
            break
    
    return answer

결과