프로그래머스 - 더 맵게 문제 링크

[문제]

문제 설명

매운 것을 좋아하는 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 합니다.

입출력 예

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

---

[풀이]

해설

1. 우선순위큐를 이용하여 가장 작은 값과 그 다음 값을 주어진 규칙에 맞게 계산하여 새로 queue에 입력하는 while문을 돌린다.
2. 큐의 사이즈가 2개 아니거나(계산식을 이요할 수 없음) 큐의 최소값(peek())이 이미 K에 도달하였다면 while문을 정지시키고 while문을 돌리 때 카운팅하였던 값을 반환한다.
3. 단 큐의 while문을 탈출했을 때의 queqe.peek() 값이 K보다 작다면(주어진 scoville로는 K에 도달할 수 없는 경우) -1를 반환한다.
   

코드

public int solution(int[] scoville, int K) {
	int answer = 0;

	PriorityQueue<Integer> queue = new PriorityQueue<Integer>();

	for (int s : scoville)
			queue.offer(s);

	while (queue.size() > 1 && queue.peek() <= K) {
		queue.offer(queue.poll() + queue.poll() * 2);
		answer++;
	}

	return queue.peek() > K ? answer : -1;
}