[프로그래머스] 더 맵게 java 자바

문제

문제 설명

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

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

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

제한 사항

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

풀이

문제에서 Leo씨가 가장 낮은 스코빌 지수 두 개를 섞어서 새로운 방법으로 음식을 만든다고 했기 때문에 우선순위큐를 사용해서 풀면 쉽게 풀 수 있습니다(문제 유형에도 그렇게 적혀있...)

우선순위 큐 : 우선순위를 가진 원소들을 저장하는 큐 로, FIFO 순서가 아니라 우선 순위가 높은 항목이 먼저(들어온 순서에 상관없이 가장 우선순위가 높은 항목) 제거되는 큐를 말합니다.

우선순위가 가장 높은 값 (=스코빌 지수가 낮은 값) 을 t1에 저장하고 t2에는 그 다음으로 우선순위가 가장 높은 값을 가져와서 섞어주는 연산을 진행합니다.

이때 원래의 값을 새로운 값으로 대체해야 하기 때문에 peek이 아닌 poll을 사용해줍니다.

(저는 안 풀어봤지만 우선순위큐가 아닌 그냥 큐를 사용하면 효율성에 어긋난다고 하는 것 같아요)

코드

package Level2;

import java.util.*;
public class 더맵게 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		System.out.println(solution(new int[] {1,2,3,9,10,12}, 7));
	}
	
	public static int solution(int[] scoville, int K) {
		int answer=0;
		
		PriorityQueue<Integer>heap=new PriorityQueue<>();
		for(int s:scoville) {
			heap.offer(s);
		}
		
		while(heap.peek()<K) {
			if(heap.size()<2)return -1;
			int t1=heap.poll();
			int t2=heap.poll();
			
			int newSco=t1+2*t2;
			heap.offer(newSco);
			answer++;
		}
		
		
		return answer;
	}
}