프로그래머스 더 맵게(scoville) 정답 코드

난이도 ★★★☆☆

 

문제를 보시려면 여기를 클릭

 

 

 

틀리기 쉬운 입출력 예제

입력	출력
{0}, 0 {0}, 1 {1, 1, 1}, 7 {1, 1, 1}, 8	0 -1 2 -1

 

 

 

힌트

정렬대신 TreeMap을 꼭 써야합니다.   매번 정렬하면 그때마다 O(N logN)이 들어가지만, TreeMap을 이용하면 그때마다 O(logN)만 들어갑니다.

 

 

 

이하는 코드입니다.

import java.util.TreeMap;
 
public class Solution {
    public int solution(int[] scoville, int K) {
        TreeMap<Integer, Integer> scovilleCountMap = new TreeMap<>(); // 중복입력에 대응하기 위해 Set이 아닌 Map
 
        for (int num : scoville) {
            push(num, scovilleCountMap);
        }
 
        int answer = 0;
 
        while (true) {
            int min = popMin(scovilleCountMap);
 
            if (min >= K) {
                break;
            }
 
            Integer nextMin = popMin(scovilleCountMap);
 
            if (nextMin == null) {
                answer = -1;
                break;
            }
 
            int newNum = min + (nextMin * 2);
            push(newNum, scovilleCountMap);
 
            answer++;
        }
 
        return answer;
    }
 
    private Integer popMin(TreeMap<Integer, Integer> countMap) {
        if (countMap.isEmpty()) {
            return null;
        }
 
        int min = countMap.firstKey();
        int count = countMap.get(min);
 
        if (count > 1) {
            countMap.put(min, count - 1);
        } else {
            countMap.remove(min);
        }
 
        return min;
    }
 
    private void push(int num, TreeMap<Integer, Integer> countMap) {
        Integer count = countMap.get(num);
 
        if (count == null) {
            countMap.put(num, 1);
        } else {
            countMap.put(num, count + 1);
        }
    }
}