[프로그래머스 코딩테스트] 더 맵게

Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.
섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

• 스코빌 지수가 1인 음식과 2인 음식을 섞음
  새로운 음식의 스코빌 지수 = 1 + (2 * 2) = 5
  가진 음식의 스코빌 지수 = [5, 3, 9, 10, 12]

• 스코빌 지수가 3인 음식과 5인 음식을 섞음
  새로운 음식의 스코빌 지수 = 3 + (5 * 2) = 13
  가진 음식의 스코빌 지수 = [13, 9, 10, 12]

이때 13은 이미 k값을 넘겼기에 answer은 2가 된다.

내 코드

import java.util.*;

class Solution {
    public int solution(int[] scoville, int k) {
        int answer = 0;
        PriorityQueue<Integer> q = new PriorityQueue<>();
        for(int a : scoville) q.offer(a);
        
       while(q.peek() < k){
            if(q.size() < 2) return -1;
            else{
                int first = q.poll();
                int second = q.poll();
                
                q.offer(first + (second*2));
                answer++;
                
            }
        }
        
        return answer;
    }
}

정렬을 해주기 위해 PriorityQueue 자료구조를 사용했다.
입력받아진 scoville 배열의 값들을 우선 큐에 넣어준 뒤 q의 가장위의 값이 k보다 작을 동안 반복문이 돌아가며 스코빌 지수를 계산하도록 한다.

이때 큐의 크기가 2보다 작다면 스코빌 지수를 계산할 수 없기에 -1을 리턴한다.

PriorityQueue

PriorityQueue는 일반적인 큐의 구조를 가지지만 데이터가 들어온 순서대로 나가는 것이 아닌 우선순위가 높은 데이터가 먼저 나가는 자료구조이다.

내부적으로 compareTo 메서드를 오버라이드하여 우선순위 조건을 리턴해 우선순위가 높은 객체를 추출해준다.

PriorityQueue는 Heap을 이용해 구현하는 것이 일반적이다.
데이터 삽입 시 최대힙 혹은 최소 힙을 구성한다.