프로그래머스 Level 2 - Heap - 더 맵게

문제 설명

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

 

---

 

저는 자바의 우선순위 큐를 이용하여 풀이하였습니다.

 

1. 우선순위 큐 에 음식 배열 값 넣기

2. while문을 이용하여 조건( 모든 음식의 스코빌 지수가 K 이상) 일 때 까지 반복문 수행

3. while 조건 동안 우선순위 큐의 첫번째 , 두번째 요소를 꺼내어 해당 규칙으로 섞은 음식의 스코빌 지수를 구합니다.

(우선순위 큐는 별도의 정렬 없이 오름차순으로 정렬이 되기 때문에 poll() 연산 두번으로 요소들을 꺼낼 수 있습니다.)

4.조건을 충족하지 못할 경우를 대비하여 우선순위 큐 의 요소가 1개일 때 값이 K를 넘지 못한다면 -1을 리턴해줍니다.

5.위의 규칙들을 지키며 새 스코빌 지수를 우선순위 큐에 넣어 반복하며 count 해줍니다.

 

아래는 코드입니다.

 

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
        
        for(int i=0; i<scoville.length; i++){
            pq.add(scoville[i]);
        }
        
        while(true){
            
          if(pq.peek() >= K){
                break;
            }
            
            int first = pq.poll();
            int second = pq.poll();
            
            int val = first + (second * 2);
            
            if(pq.size() == 1 && pq.poll() < K){
                return -1;
            }
            
            pq.add(val);
            answer++;

        }
        
        return answer;
    }
}