[Java 알고리즘], 프로그래머스 더 맵게, level2, PriorityQueue(우선순위 큐)

더 맵게

문제 설명

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

 

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

 

제한 사항

- scoville의 길이는 1 이상 1,000,000 이하입니다.
- K는 0 이상 1,000,000,000 이하입니다.
- scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
- 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

 

입출력 예

scoville	K	return
[1, 2, 3, 9, 10, 12]	7	2

 

입출력 예 설명

스코빌 지수가 1인 음식과 2인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
새로운 음식의 스코빌 지수 = 1 + (2 * 2) = 5
가진 음식의 스코빌 지수 = [5, 3, 9, 10, 12]

스코빌 지수가 3인 음식과 5인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
새로운 음식의 스코빌 지수 = 3 + (5 * 2) = 13
가진 음식의 스코빌 지수 = [13, 9, 10, 12]

모든 음식의 스코빌 지수가 7 이상이 되었고 이때 섞은 횟수는 2회입니다.

 

나의 풀이

import java.util.PriorityQueue;

class Solution {
   public int solution(int[] scoville, int K) {
        int answer = 0;
        PriorityQueue<Integer> heap = new PriorityQueue<Integer>();
        
        for (int aScoville : scoville) {
            heap.add(aScoville);
        }
        while(heap.peek() < K) {
        	if(heap.size() == 1) return -1;
        	
        	//섞는다.
        	int val1 = heap.poll();
        	int val2 = heap.poll();
        	
        	int result = val1 + (val2*2);
        	
        	heap.add(result);
        	answer ++;
        }
        return answer;
   }
}

- 우선순위 큐를 활용하여 쉽게 풀 수 있는 문제였습니다. 우선순위 큐는 큐의 일종이지만 기존 큐와 다른점은 기존의 선입선출하지 않고 우선순위가 높은 순서대로 반환하는 것입니다.

- 스코빌로 들어온 배열을 우선순위큐에 저장합니다. 이때 우선순위에 따라 저장됩니다.

- 가장 우선순위가 높은(작은값) 값이 peek()에 의해서 K와 비교되며 while의 조건절에 들어가게 됩니다. K보다 작은 경우는 섞어줘야 하는 단계이기 때문에 아래의 로직을 수행합니다.

- poll() 메소드는 우선순위큐에서 데이터를 뽑아옵니다(우선순위가 높은 순서대로 뽑아옵니다.) 

- 가장작은값 + (두번째 작은값 *2) 의 결과를 result에 담게 되고 이를 우선순위 큐에 담게되면 또다시 우선순위에 따라 heap이라는 우선순위 큐에 정렬됩니다.

 

- 대부분의 사람들이 우선순위 큐를 활용하여 풀이를 해결하였습니다. -1을 리턴할때의 처리만 다를뿐 로직의 뼈대는 우선순위 큐를 활용하여 val1 과 val2를 통해 result 값을 구하는 로직은 같았습니다.