프로그래머스: 귤 고르기(우선순위 큐 Priority Queue)

import java.util.*;

class Solution {
    public int solution(int k, int[] tangerine) {
        /*
        예를 들어, 경화가 수확한 귤 8개의 크기가 
        [1, 3, 2, 5, 4, 5, 2, 3] 이라고 합시다. 
        경화가 귤 6개를 판매하고 싶다면, 
        크기가 1, 4인 귤을 제외한 여섯 개의 귤을 상자에 담으면, 
        귤의 크기의 종류가 2, 3, 5로 총 3가지가 되며 
        이때가 서로 다른 종류가 최소일 때입니다.
        */
        Map<Integer, Integer> map = new HashMap<>();
        for (int t : tangerine) {
            map.put(t, map.getOrDefault(t, 0) + 1);
        }

        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> map.get(b) - map.get(a));
        pq.addAll(map.keySet());
		
        int count = 0;
        while (k > 0) {
        	/*
                [2, 5, 3, 4, 1]
                t = 2 
                [5, 1, 3, 4]
                t = 5 
                [3, 1, 4]
                t = 3 
                반환값: 3
        	*/
            int t = pq.poll();
            int num = Math.min(map.get(t), k);
            // 맵에 있는 값 재 업데이트
            map.put(t, map.get(t) - num);
            //총 k개만 담을 수 있으니까, 담은 사이즈 개수는 k에서 빼줘야겠지? ㅇㅇ
            k -= num; 
            if (map.get(t) > 0) {
                pq.add(t);
            }
            count++;
        }

        return count;
    }



    public static void main(String[] args) {
        int k = 6;
        int[] tangerine = {1, 3, 2, 5, 4, 5, 2, 3};
        
        Solution sol = new Solution();
        int result = sol.solution(k, tangerine);
        System.out.println(result); 
    }
}

이 문제의 핵심은 "k개의 귤을 고를 때, 가능한 한 다양한 종류의 귤을 적게 선택하려면 어떻게 해야 하는가?"입니다.

이를 위해 우선 각 귤 크기별로 개수를 세어 Map에 저장합니다. 이 Map의 key는 귤의 크기, value는 해당 크기의 귤 개수입니다.

그 다음, 우선순위 큐를 사용하여 가장 많은 개수를 가진 귤 크기부터 선택합니다. 우선순위 큐는 항상 가장 우선순위가 높은 원소를 먼저 반환합니다. 이 경우, 우선순위는 귤의 개수이며, 많은 개수를 가진 귤이 높은 우선순위를 가집니다.

이제 k개의 귤을 고를 때까지 다음 과정을 반복합니다:

1. 우선순위 큐에서 가장 많은 개수를 가진 귤을 선택합니다.
2. 선택한 귤의 개수와 남아있는 귤(k) 중 작은 수만큼 귤을 고릅니다.
3. 고른 귤의 개수만큼 k를 줄이고, 고른 귤의 개수를 Map에서 빼줍니다.
4. 만약 고른 귤이 아직 Map에 남아있다면, 다시 우선순위 큐에 넣습니다.
5. 고른 귤의 종류 수를 세서 count에 더합니다.

이 과정을 반복하면, k개의 귤을 고를 때 크기가 서로 다른 종류의 수의 최솟값을 구할 수 있습니다. 이 값이 곧 함수의 반환값이 됩니다.