[프로그래머스] 귤 고르기

📚 문제 설명

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

🔎 입출력 예

💻 처음으로 푼 코드

처음에 귤을 box 배열에 크기별로 분류해서 담은 후 box을 정렬해서 계산해줬다. 하지만 런타임 에러가 발생했다...

import java.util.*;
class Solution {
    public int solution(int k, int[] tangerine) {
        int answer = 0;
        
        int[] box = new int[10000000]; // 개수 셀 배열
        
        for(int i=0; i<tangerine.length; i++) {
            box[tangerine[i]]++;
        }
        
        Arrays.sort(box);
        for(int i=box.length-1; i>=0; i--) {
            if(k>0) {
                k-=box[i];
                answer++;
            } else {
                break;
            }
        }
   
        return answer;
    }
}

다른 방식을 고민하다 map을 사용해서 풀어보자 해서 새로운 코드를 작성하였다.

💻 최종 수정 코드

import java.util.*;
class Solution {
    public int solution(int k, int[] tangerine) {
        int answer = 0;
        HashMap<Integer,Integer> map = new HashMap<>();
        
        // map에 개수 저장
        for(int t : tangerine) {
            map.put(t, map.getOrDefault(t,0) +1);
        }
        
        // map의 value만 arrayList에 저장
        ArrayList<Integer> value = new ArrayList<>(map.values());
        Collections.sort(value,Collections.reverseOrder());
        
        for(int v : value) {
            if(k > 0) {
                k -= v;
                answer++;
            } else {
                break;
            }
        }
            
        return answer;
    }
}

📖 Solution

HashMap을 사용해서 문제를 해결하였다.

1. tangerine 배열의 정수를 HashMap의 key값으로 해서 정수의 개수를 저장한다.
2. map의 value(값들)만 ArrayList에 저장한다.
3. Collections.reverseOrder()을 사용해서 내림차순으로 정렬한다.
4. 계산하여 값을 구한다.

여기서 map.getOrDefault를 사용했는데 getORDefault란 뭐냐?

찾는 키가 존재한다면 찾는 키의 값을 반환하고 없다면 기본 값을 반환하는 메서드

💡 getOrDefault(Object key, V DefaultValue)

매개 변수 : 이 메서드는 두 개의 매개 변수를 허용한다.

key : 값을 가져와야 하는 요소의 키
defaultValue : 지정된 키로 매핑된 값이 없는 경우 반환되어야 하는 기본값

찾는 key가 존재하면 해당 key에 매핑되어 있는 값을 반환하고, 그렇지 않으면 디폴트 값이 반환된다!