[Programmers] 귤 고르기

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

프로그래머스

문제 설명

k개의 귤을 고를 때 크기별로 분류 시 크기가 다른 종류가 최소가 되도록 해야 한다. 이때 종류의 개수를 구해야 한다. 처음 문제를 보았을 땐 배열로 카운트할까 생각했지만 원소로 어떤 숫자가 들어올지 몰라 초기화하기 까다로웠다. 그래서 숫자별로 그룹핑할까 생각했지만 이 또한 적절하지 않다고 생각했다. 마지막으로 결정한 방법은 HashMap과 정렬을 활용한 방법이다. 먼저 주어진 tangerine 배열을 순회하면서 HashMap에 숫자를 키, 개수를 값으로 저장한다. 그러면 크기별 개수를 카운팅할 수 있다. 그다음 HashMap.values()를 사용하여 값으로 구성된, 즉 크기별 개수로 구성된 리스트를 얻는다. 그 다음 내림차순으로 정렬하면 개수가 가장 많은 크기 종류 순서대로 조회할 수 있다. 마지막으로 정렬된 리스트를 순회하면서 k에서 크기별 숫자를 빼주고 횟수를 저장한다. 빼나가다가 0보다 작거나 같은 경우가 되면 그때까지 반복한 횟수가 최소한의 크기별 개수가 된다.

코드

import java.util.Map;
import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;

class Solution {
    public int solution(int k, int[] tangerine) {
        Map<Integer, Integer> map = new HashMap<>();
        
        for (int elem: tangerine) {
            if (!map.containsKey(elem)) {
                map.put(elem, 1);
                continue;
            }
            
            map.put(elem, map.get(elem) + 1);
        }
        
        List<Integer> theNumber = new ArrayList<>(map.values());
        
        Collections.sort(theNumber, Collections.reverseOrder());
        
        int answer = 0;
        for (int number: theNumber) {
            k -= number; answer++;
            if (k <= 0) break;
        }
        
        return answer;
    }
}