프로그래머스 lv2 귤 고르기

문제 링크

귤 고르기

풀이

• 처음에는 조합문제라고 생각했다. 왜냐면 주어진 귤의 개수 중에서 조합의 수가 적은 순으로 골라내야하는 것이었으니까
• 그런데 다르게 생각해보니 더욱 쉬웠다.
• 가장 적은 수의 종류를 뽑아내는 방법은, 애초에 많은 귤을 가진 사이즈를 기준으로 정렬해서 앞에서부터 제거해나가면 되는 것이었다. 그런 다음 귤의 개수가 0과 같거나 작아지면 그때 종료하면 된다.

import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.stream.Collectors;

public class 귤고르기 {
    public int solution(int k, int[] tangerine) {
        int answer = 0;

        HashMap<Integer, Integer> sizeMap = new HashMap<>();
        Arrays.stream(tangerine)
                .forEachOrdered(size -> {
                    sizeMap.put(size, sizeMap.getOrDefault(size, 0) + 1);
                });

        // 가장 적은 수의 종류를 뽑아내는 방법은, 애초에 많은 귤을 가진 사이즈를 기준으로 정렬해서 제거해나가면 된다.
        // 조건은 귤의 개수가 총 k가 되어야 함.
        List<Integer> sortedKeySet = sizeMap.keySet().stream()
                .sorted((o1, o2) -> sizeMap.get(o2) - sizeMap.get(o1))
                .collect(Collectors.toList());

        for (int key : sortedKeySet) {
            k -= sizeMap.get(key);
            answer++;
            if (k <= 0) {
                break;
            }
        }

        return answer;
    }

}

후기

• 단순하게 생각하지 않기