프로그래머스 lv2 더 맵게

문제 링크

더 맵게

풀이

import java.util.PriorityQueue;

class Solution {
    public int solution(int[] scoville, int k) {
        int cnt = 0;
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        for (int i : scoville) {
            priorityQueue.offer(i);
        }
        return hot(priorityQueue, cnt, k);
    }

    public int hot(PriorityQueue<Integer> queue, int cnt, int k) {
        while (queue.size() != 1) {
            cnt++;
            int first = queue.poll();
            int second = queue.poll();
            queue.add(first + (second * 2));
            if(queue.peek() > k) break;
        }
        
        if(queue.size() == 1 && queue.peek() < k) return -1;
        
        return cnt;
    }
}

소감

• 처음에는 array와 DP를 사용해서 풀었다. 테스트 케이스는 통과했지만, 효율성 테스트에서는 죄다 실패했다.
• 처음에는 왜인지 이해를 못했는데, array의 경우 무조건 배열에 대해서 정렬을 해야만 했는데, 이게 효율성에서 실패를 하게 된 원인이었다.
• 몰라서 이거저거 찾던 도중, 누가 자동으로 정렬이 되는 자료구조를 사용해보라고 힌트를 남긴 것을 보았고.. 이 문제의 카테고리가 왜 Heap으로 되어있는지를 알게 되었다.
• 큐에 들어가는 데이터의 순서가 자동으로 힙에 의해서 정렬이 되는 PriorityQueue를 통해서 문제를 풀었고, 이를 통해서 바로 통과했다.
• 처음으로 heap으로 문제를 풀어봤는데..해당 자료구조 관련해서 조금 공부가 더 필요할 것 같다.