Lv.2 귤 고르기 [JAVA]

문제 링크

성공 여부(걸린 시간): 성공(14분 29분)

아이디어

최소종류의 귤을 상자에 담기위해선 가장 많은 수를 가진 종류 순으로 넣어주면서 포장해주면 된다.
그리고 가득찼으면 끝

우선 각 크기별 개수를 저장해준다.
처음엔 카운팅소트로 개수를 세려고 했는데 원소가 1000만까지 있을 수 있으므로
배열의 크기를 1000만까지 할 수는 없기에 HashMap으로 개수를 저장해줬다.

그다음 HashMap의 keySet을 통해 우선순위큐에 귤의 종류와 개수를 class로 정의해
넣어주고 원하는 개수만큼 구하기 위해서 구할 수 있을때까지 k에서 빼주면서 pq를 뽑아주면 된다.
뽑을때마다 answer++(귤 종류)해주고 마지막에 return해주면 끝

풀이 코드

import java.util.*;

class Solution {
    static class pair {
        int kind, amount;
        public pair(int kind, int amount){
            this.kind = kind;
            this.amount = amount;
        }
    }
    public int solution(int k, int[] tangerine) {
        int answer = 0;
        HashMap<Integer, Integer> cnt = new HashMap<>();
        for(int t: tangerine){
            if(cnt.containsKey(t)){
                cnt.put(t, cnt.get(t)+1);
            }
            else{
                cnt.put(t, 1);
            }
        }
        PriorityQueue<pair> pq = new PriorityQueue<pair>(Comparator.comparingInt(o1->o1.amount*(-1)));
        for(int kind: cnt.keySet()){
            pq.add(new pair(kind, cnt.get(kind)));
        }
        while(k>0){
            pair cur = pq.poll();
            k-=cur.amount;
            answer++;
        }
        return answer;
    }
}