힙(Heap) 더맵게

프로그래머스(Heap) 더맵게

이번 문제는 남은 스코빌 지수에서 현재 작은 값을 뽑아 그 값이 K 보다 작고 2번째로 섞을 스코빌 지수가 있다면 공식에 의해 섞어서 남은 스코빌에 합쳐서 해당 방법을 반복하는 알고리즘 문제입니다. 우선순위큐라는 개념에 맞춰 로직을 구현하면 손쉽게 풀 수 있고 자바에서는 PriorityQueue를 사용해 손쉽게 알고리즘을 구현할 수 있었습니다.

public int solution(int[] scoville, int K) {
        int answer = 0;
        Queue<Integer> priorityQueue = new PriorityQueue<>();
        for (int i =0; i< scoville.length; i++) {
            priorityQueue.add(scoville[i]);
        }

        while (!priorityQueue.isEmpty()) {
            int minScoville = priorityQueue.poll();
            if (minScoville >= K) {
                break;
            } else {
                if(priorityQueue.isEmpty()) {
                    answer = -1;
                } else {
                    int secondMinScoville = priorityQueue.poll();
                    priorityQueue.add(minScoville + (secondMinScoville * 2));
                    answer++;
                }
            }
        }

        return answer;
    }