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

 

문제 설명

경화는 과수원에서 귤을 수확했습니다. 경화는 수확한 귤 중 '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가지로, 이 값이 최소가 됩니다.

 

 

 

나의 풀이

public int solution(int k, int[] tangerine) {
   int answer = 0;
   Map<Integer, Integer> map = new HashMap<>();
   
   for (int i : tangerine)
   {
      map.put(i, map.getOrDefault(i, 0) + 1);
   }
   
   List<Integer> collect = map.values().stream().sorted()
         .collect(Collectors.toList());
   
   for (int i = collect.size()-1; i >= 0; i--)
   {
      if (k > 0) {
         k -= collect.get(i);
         answer++;
      }
   }
   
   return answer;
}

이 문제를 풀 때 생각난 방법은 Map을 사용하는 것이었다..! 내가 Map 사용에 빠졌나.. 계속 방법이 Map 밖에 기억이 안남 ..ㅎㅎ 

아무튼 Map으로 귤의 사이즈를 key 값으로 두고, 귤 사이즈별 개수를 value로 두는 걸 생각했다. 

 

그리고 프로그래머스 문제 풀면서 알게 된 (?) getOrDefault 를 사용해서 key값인 귤 사이즈를 발견하면 +1 씩 해주고 아니면 기본값 0 을 넣도록 해줬다. 

 

최대한 같은 크기로 귤을 골라야 하기 때문에 다음은 이제 value 값을 기반으로 정렬을 해줬고, 한 상자에 담아야 하는 귤의 개수 k개가 0보다 클 경우까지 귤을 넣을 수 있기 때문에 k > 0 으로 해서 귤을 빼주고, 다음 answer 을 1씩 증가해주면 된다! 

 

 

 

다른 사람 풀이

public int otherSolution(int k, int[] tangerine)
{
   int answer = 0;
   Map<Integer, Integer> map = new HashMap<>();
   
   for (int i : tangerine)
   {
      map.put(i, map.getOrDefault(i, 0) + 1);
   }
   
   List<Integer> list = new ArrayList<>(map.keySet());
   list.sort(((o1, o2) -> map.get(o2) - map.get(o1)));
   
   for (Integer key : list)
   {
      if (k > 0) {
         k -= map.get(key);
         answer++;
      }
   }
   
   return answer;
}

방법은 나랑 비슷한데 정렬해서 값을 어떻게 뽑아오는 지 이 방법이 다를 뿐!!! 

List에 map의 key값을 넣어주고, 다음 list를 정렬할 때 map에서 해당 키 값을 구해 이 값 기반으로 정렬해줬다는 점이다!! 

이런 방법도 알아둬야지~_~