[ Java ] 프로그래머스 level2 138476번 귤 고르기

귤 고르기 #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

---

입출력 예ktangerineresult

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

---

입출력 예 설명

입출력 예 #1

• 본문에서 설명한 예시입니다.

입출력 예 #2

• 경화는 크기가 2인 귤 2개와 3인 귤 2개 또는 2인 귤 2개와 5인 귤 2개 또는 3인 귤 2개와 5인 귤 2개로 귤을 판매할 수 있습니다. 이때의 크기 종류는 2가지로 이 값이 최소가 됩니다.

입출력 예 #3

• 경화는 크기가 1인 귤 2개를 판매하거나 2인 귤 2개를 판매할 수 있습니다. 이때의 크기 종류는 1가지로, 이 값이 최소가 됩니다.

나의 풀이

map : 각 무게 별로 갯수를 저장하는 HashMap

arr : 갯수 순으로 내림차순을 하기 위한 ArrayList

cur : 현재 담긴 귤의 갯수

cnt : 현재 담긴 무게의 종류 수 => 최종 리턴 값 

 

각 무게 별로 몇개씩 있는 지 갯수를 세어야 하므로, HashMap 생성하여 저장 <무게(kg), 갯수>

최소의 종류를 선택하려면 갯수가 많은 무게의 귤을 먼저 담아야 함 

갯수 순으로 내림차순이 필요, ArrayList 생성해서 갯수를 담고 내림차순으로 정렬

arr를 순회하면서 cur에 갯수만큼 증가하고, cnt를 1 증가시킴

만약 cur이 k보다 같거나 커지면 종료 (break)

import java.util.*;

class Solution {
    public int solution(int k, int[] tangerine) {
        HashMap<Integer,Integer> map = new HashMap<>();
        ArrayList<Integer> arr = new ArrayList<>();
        int cnt = 0; // 현재 담은 서로 다른 무게 종류 수
        int cur = 0; // 현재 담은 귤 갯수
        
        for(int t : tangerine){
            map.put(t,map.getOrDefault(t,0)+1);
        }
        
        for(int t : map.keySet()){
            arr.add(map.get(t));
        }
        
        Collections.sort(arr,Collections.reverseOrder());
        
        for(int t : arr){
            System.out.println(t);
            if(k > cur){
                cnt++;
                cur+=t;
            }else break;
            
        }
        return cnt;
    }
}

다른 풀이

map의 value값 자체를 넘겨주어 ArrayList를 생성하는 방법

java8 이상 부터는 ArrayList 자체에 sort 가 내장되어 있어서 Collections.sort 사용하지 않아도 됨 

import java.util.*;

class Solution {
    public int solution(int k, int[] tangerine) {
        HashMap<Integer,Integer> map = new HashMap<>();
        int cnt = 0; // 현재 담은 서로 다른 무게 종류 수
        int cur = 0; // 현재 담은 귤 갯수
        
        for(int t : tangerine){
            map.put(t,map.getOrDefault(t,0)+1);
        }
        
        ArrayList<Integer> arr = new ArrayList<>(map.values());
        arr.sort((o1,o2) -> o2 - o1);
        
        for(int t : arr){
            if(k > cur){
                cnt++;
                cur+= t;
            }else break;
            
        }
        return cnt;
    }
}

나의 풀이와 다른 풀이 비교