코딩테스트 연습 > 연습문제 > 귤 고르기

⚡ 문제 설명

경화는 과수원에서 귤을 수확했습니다. 경화는 수확한 귤 중 '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

⚡ 구현코드

import java.util.*;

class Solution {
    public int solution(int k, int[] tangerine) {
        HashMap<Integer, Integer> tanCount = new HashMap<>();
        for(int t : tangerine){
            tanCount.put(t, tanCount.getOrDefault(t, 0) + 1);
        }
        
        int answer = 0;
    
        List<Integer> values = new ArrayList<>(tanCount.values());
        values.sort(Comparator.reverseOrder());
        
        for(int v : values){
            k -= v; 
            answer ++;
            if(k <=0 ) break;
        }
        
        return answer;
    }
}

⚡ 구현코드 해설

tangerine 배열에서 귤 크기, 해당 크기의 갯수를 HashMap의 key, value로 만들었다.

여기서 나는 HashMap의 value 값을 비교하여 큰 순서대로 k값에서 빼고, 해당 key를 HashMap에서 remove 하는 방식으로 접근하였다.

그래서 발견한 방법이 아래와 같다.

value가 10보다 큰 entry가 존재하는지 확인

boolean hasValueGreaterThan10 = map.values().stream().anyMatch(value -> value > 10);

그러나 이 방식으로 하면 key, value를 각각 또 구해야하는 번거로움과 복잡함이 생긴다...

그러다가, 문득 key값은 필요가 없고 이 문제에서는 value로만 충분히 풀이가 가능하다는 사실 !!
value를 모두 모아 배열로 만들고, 역순으로 정렬하였다.
그리고 반복문을 사용해서 차례로 k에서 그 값을 빼주고, 빼준 후의 k 값이 0 이하일 경우 반복문을 빠져나오도록 하였다.

많이 돌아온 듯 하지만.. 풀고나니 뿌우둣 ✨