[프로그래머스] 귤 고르기 (Java)

문제

프로그래머스

 

 

알고리즘

해시맵

 

 

풀이

귤의 수를 크기 별로 세고, 가장 많은 귤부터 상자에 담으면서 몇 종류인지 세면 된다.

 

귤의 수를 크기 별로 셀때, 귤의 크기가 최대 10,000,000 이므로

리스트를 사용하지 않고 해시맵을 사용하여 메모리를 절약한다.

 

tangerine을 전부 탐색하고 나면 해시맵에 귤의 크기와 개수가 저장되어있으므로

크기 별 귤의 개수인 map.values() 를 리스트에 저장해 내림차순으로 정렬하고,

k가 넘을 때까지 원소를 더하며 몇 종류를 담았는지 count를 증가시킨다.

 

 

코드

import java.util.*;

class Solution {
    public int solution(int k, int[] tangerine) {
        List<Integer> values =  new ArrayList<>();
        Map<Integer, Integer> map = new HashMap<>();
        
        for(int t: tangerine)
            map.put(t, map.getOrDefault(t, 0) + 1);
    
        for(int value: map.values())
            values.add(value);
        Collections.sort(values, Collections.reverseOrder());
        
        int sum = 0;
        int count = 0;
        for(int value: values) {
            sum += value;
            count++;
            if(sum >= k) break;
        }
        
        return count;
    }
}