[프로그래머스] Lv.2 귤 고르기 (Java 풀이 - 2가지)

프로그래머스 - 귤 고르기 (Java) 

 

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

입출력 예 설명

입출력 예 #1

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

입출력 예 #2

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

입출력 예 #3

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

 

 

---

 

문제 풀이 (Java)

 

마지막에 최종 풀이 있습니다.

 

 

1. 첫번째 풀이 (시간초과)

 

정말 고민을 많이하고 찾아보고 결국 풀었는데 34개 테스트중 6개 시간초과

import java.util.*;
import java.util.Map.*;

class Solution {
    public int solution(int k, int[] tangerine) {
        int answer = 0;
        
        Map<Integer, Integer> sizeMap = new HashMap<Integer, Integer>();
        
        // Comparator 정의
        Comparator<Entry<Integer, Integer>> comparator = new Comparator<Entry<Integer, Integer>>() {
            @Override
            public int compare(Entry<Integer, Integer> e1, Entry<Integer, Integer> e2) {
                return e1.getValue().compareTo(e2.getValue());
            }
        };
        
        /* 1. 귤 사이즈별로 정리 */
        for(int size : tangerine) {
            sizeMap.put(size, sizeMap.getOrDefault(size, 0)+1);
        }
        
        /* 2. 사이즈별로 가장 많은 귤들부터 담기 */
        while(k > 0) {
            Entry<Integer, Integer> maxEntry = Collections.max(sizeMap.entrySet(), comparator); // Max Value의 key, value

            k -= maxEntry.getValue(); // 박스에 담았으니 그만큼 줄임
            answer++; // 종류별로 ++
            sizeMap.put(maxEntry.getKey(), 0); // 해당 key는 0으로 초기화
        }

        return answer;
    }
}

 

---

2. 두번째(성공) 풀이

 

아래 풀이는 sort에 대해 이해가 안되는 경우 참고하시기 바랍니다.

import java.util.*;
import java.util.Map.*;

class Solution {
    public int solution(int k, int[] tangerine) {
        int answer = 0;
        
        Map<Integer, Integer> sizeMap = new HashMap<Integer, Integer>();
        
        // 귤 사이즈별로 정리
        for(int size : tangerine) {
            sizeMap.put(size, sizeMap.getOrDefault(size, 0)+1);
        }
        
        // keyList 생성
        List<Integer> keyList = new ArrayList<>(sizeMap.keySet());
        
        // keyList의 value 기준 내림차순 정렬
        keyList.sort(new Comparator<Integer>() {
            @Override
            public int compare(Integer arg0, Integer arg1) {
                int age0 = sizeMap.get(arg0);
                int age1 = sizeMap.get(arg1);
                  
                if (age0 == age1) return 0;
                else if (age0 < age1) return 1;
                else return -1;
            }
        });
        
        // 아래코드와 위 내림차순 정렬은 같은 코드이다.
        // keyList.sort((o1, o2) -> sizeMap.get(o2) - sizeMap.get(o1)); // 내림차순 정렬
        
        int i = 0;
        while(k > 0){
            k -= sizeMap.get(keyList.get(i));
            answer++;
            i++;
        }

        return answer;
    }
}

---

 

3. 최종 소스(성공)

 

import java.util.*;
import java.util.Map.*;

class Solution {
    public int solution(int k, int[] tangerine) {
        int answer = 0;
        Map<Integer, Integer> sizeMap = new HashMap<Integer, Integer>();
        
        // 1. sizeMap data set (귤 사이즈별로 정리)
        for(int size : tangerine) {
            sizeMap.put(size, sizeMap.getOrDefault(size, 0)+1);
        }
        
        // 2. keyList 생성 (사이즈별 list)
        List<Integer> keyList = new ArrayList<>(sizeMap.keySet());
        
        // 3. keyList의 value 기준 내림차순 정렬 (사이즈별 총개수 내림차순 list로 만들어줌)
        keyList.sort((o1, o2) -> sizeMap.get(o2) - sizeMap.get(o1));
        
        // 4. k의 개수만큼 상자에 담으며 최소값 추출
        int i = 0;
        while(k > 0){
            k -= sizeMap.get(keyList.get(i));
            answer++;
            i++;
        }
        return answer;
    }
}