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

문제 설명

경화는 과수원에서 귤을 수확했습니다. 경화는 수확한 귤 중 'k'개를 골라 상자 하나에 담아 판매하려고 합니다. 그런데 수확한 귤의 크기가 일정하지 않아 보기에 좋지 않다고 생각한 경화는 귤을 크기별로 분류했을 때 서로 다른 종류의 수를 최소화하고 싶습니다.

예를 들어, 경화가 수확한 귤 8개의 크기가 [1, 3, 2, 5, 4, 5, 2, 3] 이라고 합시다. 경화가 귤 6개를 판매하고 싶다면, 크기가 1, 4인 귤을 제외한 여섯 개의 귤을 상자에 담으면, 귤의 크기의 종류가 2, 3, 5로 총 3가지가 되며 이때가 서로 다른 종류가 최소일 때입니다.

경화가 한 상자에 담으려는 귤의 개수 k와 귤의 크기를 담은 배열 tangerine이 매개변수로 주어집니다. 경화가 귤 k개를 고를 때 크기가 서로 다른 종류의 수의 최솟값을 return 하도록 solution 함수를 작성해주세요.

제한사항

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

입출력 예

k	tangerine	result
6	[1, 3, 2, 5, 4, 5, 2, 3]	3
4	[1, 3, 2, 5, 4, 5, 2, 3]	2
2	[1, 1, 1, 1, 2, 2, 2, 3]	1

Solution

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

class Solution {
    public int solution(int k, int[] tangerine) {
        int answer = 0;
        Map<Integer, Integer> map = new HashMap<>();

        for( int i : tangerine){
            map.put(i, map.getOrDefault(i, 0) + 1);
        }

        List<Integer> list = new ArrayList<>(map.keySet());
        list.sort((o1, o2) -> map.get(o2) - map.get(o1));

        for(Integer x : list){
            k -= map.get(x);
            answer++;
            if(k <= 0){
                break;
            }
        }

        return answer;
    }
}

가장 최소한의 종류가 나오는 방법은, 최대한 많은 수를 차지하는 크기인 귤 들만 남기는 것이다.
첫 번쨰 입출력 예를 살펴보자. 알아보기 쉽게 정리해서 표현하면 아래와 같다.

1 2 2 3 3 4 5 5

귤의 총 갯수는 8개다. 여기서 6개만 챙길 때, 가장 적은 서로 다른 종류의 수를 구하는 법. 어렵게 생각할 것 없다. 갯수가 큰 녀석들 기준으로 최대한 구성하면 그만이다.

1 - 1
2 - 2
3 - 2
4 - 1
5 - 2

각 귤 크기별로 갯수를 정리하면 다음과 같고, 갯수 순으로 내림차순 정렬을 하면 아래와 같다.

2 - 2
3 - 2
5 - 2
1 - 1 
4 - 1

우리는 정렬을 통해 어떤 Key 값의 데이터가 더 작은 지 알 수 있다. 아래의 코드를 주목해보자.

Map<Integer, Integer> map = new HashMap<>();

for( int i : tangerine){
    map.put(i, map.getOrDefault(i, 0) + 1);
}

List<Integer> list = new ArrayList<>(map.keySet());
list.sort((o1, o2) -> map.get(o2) - map.get(o1));

현재 귤들의 데이터들을 통해 HashMap을 생성한 후 해당 HashMap의 키 값들을 List로 따로 뺀 후, 해당 리스트를 정렬하는데 HashMap의 값을 기준으로 정렬한다.
HashMap 그 자체를 정렬할 때 여러가지 방법이 있지만, EntrySet 그 자체를 List로 뽑아와서 정렬하는 방법으로 처음에 문제를 해결했다가 너무 느려서 다른 방법을 생각해보았다. 애초에 데이터들을 변환하는 과정을 최대한 줄이고 정렬 조건을 참조하는 식으로만 개발해도 괜찮은 코드로 변한다.

for(Integer x : list){
    k -= map.get(x);
    answer++;
    if(k <= 0){
       break;
    }
}

return answer

list 에는 key의 value 값이 큰 순서대로의 key들이 정렬된 채 저장되어있다. 해당 key를 하나하나 꺼내면서 k값을 줄여나간다. k 개만큼의 세트를 만들어야 하니까 갯수가 큰 녀석들을 우선으로 제거하면 가장 최소한의 종류를 가진 세트를 만들어 낼 수 있다.