문제

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

---

입력

• 화가 한 상자에 담으려는 귤의 개수 k
• 귤의 크기를 담은 배열 tangerine

---

출력

• 귤 k개를 고를 때 크기가 서로 다른 종류의 수의 최솟값

---

풀이

제한조건

• 1 ≤ k ≤ tangerine의 길이 ≤ 100,000
• 1 ≤ tangerine의 원소 ≤ 10,000,000

접근방법

자료구조 응용, 정렬

k개의 귤을 최대한 같은 종류로 골랐을 때, 몇 가지 종류로 할 수 있는가? 를 묻는 문제이다.
따라서 귤을 선택할 때, 최대한 많이 가지고 있는 종류의 귤부터 채운다면 문제의 조건을 충족한다.

우선 각 종류의 귤이 몇 개 있는지 세어보자.
원소가 1000만까지 존재할 수 있으므로 단순 배열 선언으로는 확인하기 힘들다.
또한 길이는 최대 10만으로, 충분히 희소할 수 있으므로 Map을 이용해서 카운팅 해주자.

for(int value : tangerine)
            map.put(value, map.getOrDefault(value, 0) + 1);

이제 map을 정렬해보자. 우리는 갯수가 많은 귤부터 우선적으로 선정할 것이므로, 개수(value)순으로 정렬한다.

List<Integer> keys = new ArrayList(map.keySet());
        keys.sort((a,b) -> map.get(b) - map.get(a));

이제 k개 만큼 카운팅하며, 종류를 세어보자.

int answer = 0;
        for(int i : keys){
            answer++;
            k -= map.get(i);
            if(k <= 0)
                break;
        }

---

코드

import java.util.*;

class Solution {
    Map<Integer, Integer> map = new HashMap();
    public int solution(int k, int[] tangerine) {
        for(int value : tangerine)
            map.put(value, map.getOrDefault(value, 0) + 1);
        
        List<Integer> keys = new ArrayList(map.keySet());
        keys.sort((a,b) -> map.get(b) - map.get(a));
        
        int answer = 0;
        for(int i : keys){
            answer++;
            k -= map.get(i);
            if(k <= 0)
                break;
        }
        return answer;
    }
}