[그리디][lv.2] 귤 고르기 (Java)

https://school.programmers.co.kr/learn/courses/30/lessons/138476

프로그래머스

 

---

 

✅ 문제

 

🔑 Key Point

귤 크기별로 분류했을 떄

서로 다른 종류의 수를 최소화하고 싶다

 

문제 이해를 위해 예제를 봐보자.

K개의 귤을 담아야하는데, 

귤 리스트에 1, 3, 2, 5, 4, 5, 2, 3 사이즈의 귤들이 존재한다.

 

이때 1 (1개), 2 (2개), 3 (2개), 4 (1개),  5(2개)가 존재함을 볼 수 있다. 

총 6개를 담는 귤박스를 만든다 했을때 2, 3, 5를 넣으면 서로다른 종류의 수가 최소화된다

 

 

즉 귤의 개수로 내림차순 정렬해서,

귤 개수가 많은 순서대로 귤 박스에 넣어주면, 최소값을 찾을 수 있다!

 

 

✅ 시간복잡도 고려하기

귤의 개수는 간단하게 HashMap을 이용해서 세어주면 된다.

> 귤 전체 리스트의 최대값이 1000만이기 때문에 HashMap은 put/get이 O(1)이라서 합리적이다.

>>>  전체 귤 리스트를 한번씩 확인해서 다 처리해줘야하므로  O(N) 

 

✍️ HashMap - Value기준 정렬

//value (개수) 기준 내림차순 정렬
List<Map.Entry<Integer,Integer>> list = new ArrayList<>(count.entrySet());
list.sort((entry1, entry2) -> entry2.getValue().compareTo(entry1.getValue()));

여기에선 

- List로 변환하는 과정 -> O(N)

- 자바의 정렬에선 Timsort 알고리즘을 사용한다. 

- Timsort -> O(N Log N)

 

즉 O(N Log N)이 될것으로 예상할 수 있다.

 

 



✅ 내가 쓴 정답 코드

 

그대로 코드로 작성해주면 !

import java.util.*;
class Solution {
    public int solution(int k, int[] tangerine) {
        
        //각 사이즈별로 귤의 개수를 담는 HashMap
        HashMap<Integer, Integer> count = new HashMap<Integer, Integer>();
        
        int n = tangerine.length;
        int t = 0;
        
        //귤 사이즈 개수 체크
        for (int i=0; i<n; i++) {
            t = tangerine[i];
            
            if (count.containsKey(t)) {                
                count.put(t,count.get(t)+1);
            }
            else {
                count.put(t, 1);
            }
            
        }
        
        //value (개수) 기준 내림차순 정렬
        List<Map.Entry<Integer,Integer>> list = new ArrayList<>(count.entrySet());
        list.sort((entry1, entry2) -> entry2.getValue().compareTo(entry1.getValue()));
        
        
        // 귤 담기 (그리디)
        int answer = 0;
        
        for (Map.Entry<Integer, Integer> entry : list) {
            
            if (k <= 0)
                break;
            
            k -= entry.getValue();
            answer += 1;
            
        }

        return answer;
    }
}

 

 

 

 

 

 

 

https://kjhoon0330.tistory.com/entry/Java-List-%EC%A0%95%EB%A0%AC%EC%97%90-%EB%8C%80%ED%95%98%EC%97%AC