[프로그래머스] 더 맵게

문제

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

풀이

우선순위 큐를 이용하여 풀었다.
우선순위 큐를 이용하면 값이 삽입되고 제거될 때마다 힙 정렬을 수행하기 때문에
하나의 값을 가져올 때 가장 우선순위가 높은 것을 가져오게 되어 있다. (여기서는 가장 작은 값)
그래서 문제에 나온대로 큐를 빼서 계산을 하고 다시 넣고 또 큐를 빼더라도 가장 작은 값이 나오게 되어있다.
그래서 값을 뺄 때 K값보다 작으면 answer를 리턴해주면 된다.
이 문제를 풀기 위해서는 아래 내용을 어느 정도 알고 있어야 한다.

우선순위 큐

가장 우선순위가 높은 데이터부터 출력해주는 큐

1. 우선순위가 가장 낮은 값이 먼저
   • 값이 입력되고 제거될 때마다 최소 힙 정렬 수행
2. 우선순위가 가장 큰 값이 먼저
   • 값이 입력되고 제거될 때마다 최대 힙 정렬 수행

힙 정렬

완전 이진트리의 한 종류이다.
최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법이다.

완전이진트리

마지막 레벨을 제외하고 모든 트리가 채워져 있는 이진트리

코드

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        
        // 우선순위 큐 생성
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

		// 우선순위 큐에 배열 값을 담는다.
        for (int x : scoville) {
            priorityQueue.offer(x);
        }

		// 우선순위 큐를 순회한다.
        while (!priorityQueue.isEmpty()) {
        	// 첫번 째 값을 뺀다. (여기서 언제나 가장 작은 값이 나오게 되어있다.
            Integer first = priorityQueue.poll();
            
            // 값이 K보다 작다면 두번째 값을 뺀다.
            if (first < K) {
            
            	// 문제에 나온대로 계산하고 다시 우선순위 큐에 넣어준다.
                if (!priorityQueue.isEmpty()) {
                    Integer second = priorityQueue.poll();
                    int result = first + (second * 2);
                    priorityQueue.offer(result);
                    
                    // 연산을 할때마다 answer에 값을 1씩 증가시켜준다.
                    answer++;
                } else {
                    return -1;
                }
            } else {
                return answer;
            }
        }

        return answer;
    }
}