[Programmers] 귤 고르기 (HashMap, PriorityQueue)

 

- 목차

 

문제 설명.

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 함수를 작성해주세요.

 

 

문제 분석.

숫자 배열에서 N 개만큼의 숫자를 선택합니다.

숫자를 선택하는 조건은 최대한 적은 카테고리를 유지하는 관점으로 숫자를 선택해야합니다.

예를 들어, [1, 2, 3, 4, 5, 5] 6개의 숫자 배열에서 2개의 숫자를 고른다고 합니다.

배열에서 5가 유일하게 중복된 값을 가집니다.

그래서 5를 2개 선택하는 것이 최대한 적는 양의 카테고리를 유지하는 방향입니다.

 

저는 이러한 문제는 해결하기 위해서 HashMap 를 사용하였구요.

중복된 숫자의 개체수가 적은 숫자를 빠르게 탐색하기 위하여 PriorityQueue 를 사용하였습니다.

 

 

문제 풀이.

import java.util.*;

class Solution {
  public int solution(int k, int[] tangerine) {
    int answer = 0;
    HashMap<Integer, Integer> sizeAndCountMap = new HashMap<>();
    for (int one : tangerine) {
      sizeAndCountMap.computeIfPresent(one, (key, value) -> value + 1);
      sizeAndCountMap.putIfAbsent(one, 1);
    }

    PriorityQueue<int[]> lowCountQueue = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);
    for (Map.Entry<Integer, Integer> entry : sizeAndCountMap.entrySet()) {
      lowCountQueue.add(new int[]{entry.getKey(), entry.getValue()});
    }

    int removeCount = tangerine.length - k;
    while (removeCount > 0) {
      int[] sizeAndCount = lowCountQueue.poll();
      int size = sizeAndCount[0];
      int count = sizeAndCount[1];
      int minus = Math.min(count, removeCount);

      sizeAndCountMap.computeIfPresent(size, (s, v) -> v - minus);
      if (sizeAndCountMap.get(size) <= 0) sizeAndCountMap.remove(size);

      removeCount = removeCount - minus;
    }

    answer = sizeAndCountMap.size();
    return answer;
  }
}