[프로그래머스 *Java] - 더 맵게

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

프로그래머스

 

조건

제한 시간 : 45분 (성공)

한 번 풀었던 문제고, 전에 풀면서 삽질을 굉장히 많이했던 문제라 빠르게 접근해서 풀었다.
전에 풀었던 방식은...
ArrayList, List 를 가지고 정렬 후 제거, 삽입을 반복했는데 시간초과가 났고,
이후에 heap 문제인 걸 알고, 직접 heap 을 구현해서 풀었는데도 시간초과가 났었다.
우선순위 큐를 이용하면 내부 동작이 최대힙으로 구현되어 정렬되기 때문에 시간복잡도 효율이 좋은 걸 배웠던 문제였다.

그리고 이번에 풀었을 땐, 그 사실을 알고 바로 접근해서 푼 문제였다.

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int i = 0; i < scoville.length; i++) {
            pq.add(scoville[i]);
        }
        
        while (pq.size() > 1) {
            if(pq.peek() >= K) {
                return answer;
            }else {
                int leastSpicy = pq.poll();
                int secondLeastSpicy = pq.poll();
                int mixScoville = leastSpicy + (secondLeastSpicy * 2);
                pq.add(mixScoville);
                answer++;
            }            
        }
        
        if (pq.size() == 1 && pq.peek() > K) 
            return answer;
        
        return -1;
    }
}