[프로그래머스 Lv2.] 귤 고르기 | Java

문제 설명

문제 바로가기 클릭! 🖱️

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

풀이과정

이 문제를 딱 본 순간, 일단 HashMap 으로 해결해야겠다는 생각이 딱 들었다!

주어진 배열의 정수를 HashMap의 key값으로 해서 해당 정수의 개수를 저장하는 것까지는 생각을 해냈는데, 이 저장된 정수를 어떻게 많은 순서대로 끊어서 분류를 하지? 라는 고민을 하기 시작했다.

나는 이 귤이 숫자 몇 번의 귤인지를 구분해낼 수도 있어야 한다고 생각을 했는데, 문제에서는 이 귤이 어느 정수의 귤인지는 신경쓰지 않고 그저 몇 개의 정수가 들어갔는지를 물어보고 있었다.

key값(정수)은 관계없이 정수가 저장된 갯수들이 더 중요했던 것이다

1. 주어진 정수를 HashMap에 key값으로 해서 정수의 개수를 저장한다
2. value 값들을 ArrayList로 변환하고 내림차순 정렬한다
3. list를 돌면서, 귤의 개수가 k개 보다 크거나 같을 때까지 귤의 갯수를 더한다
4. 귤의 갯수를 더할 때마다 귤 종류를 세고 있는 카운트를 올려 준다
5. 세고 있던 귤 종류 카운트(answer)을 반환한다

정답 코드

import java.util.*;

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

성능 요약

메모리 : 88.3 MB
시간 : 46.09 ms