[Programmers] Level 2 : 귤 고르기

프로그래머스

간단한 문제이지만, ArrayList를 정렬하는 문법이 익숙치 않아 조금 걸렸다. 

구하고자 하는 것은 최대한 작은 종류의 귤을 사용해 k를 맞출 수 있는가? 이다. 탐욕법으로 접근해보면, 가장 개수가 많은 귤의 종류부터 선택하면 될것이다. 이 방법으로 구한 귤의 종류보다 절대 적게 k를 맞출 수 없기 때문이다.

그래서 귤의 종류별로 개수를 관리하는 Map을 하나 만들고, Map에 들어있는 value를 기준으로 내림차순 정렬을 해준다. 그다음 배열의 앞에서부터 귤을 제공하고, k가 넘어가는 순간 종료하면 된다.

 

import java.util.*;

class Solution {
    
    private Map<Integer, Integer> count = new HashMap<>();
    private Set<Integer> getList = new HashSet<>();
    
    public int solution(int k, int[] tangerine) {
        int answer = 0;
        for(int tang : tangerine) {
            if (count.get(tang) == null) {
                count.put(tang, 1);
            } else {
                count.put(tang, count.get(tang) + 1);
            }
        }
        List<Integer> list = new ArrayList<>(count.keySet());
        Collections.sort(list, new customComparator());
        
        for(Integer num : list) {
            if (k <= 0) break;
            answer++;
            k -= count.get(num);
        }
        return answer;
    }
    
    public class customComparator implements Comparator<Integer> {
        @Override
        public int compare(Integer a, Integer b) {
            return count.get(b).compareTo(count.get(a));
        }
    }
}