[JAVA] Heap Lv.1 / 더 맵게

[문제]

[입출력 예]

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

 

 [제한 조건]

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

[알고리즘]

Heap(우선 순위 큐)을 사용하여 간단하게 해결할 수 있는 문제이다 , scoville의 값을 모두 heap에 넣어주고
몇가지 조건만 신경써서 조건문을 걸어주면 되는 문제

• heap의 가장 앞의 값이 K이상일 동안 반복해서 실행되게 작성
• heap의 크기가 2보다 작을경우 -1 return 

 heap에서 poll을 실행하여 가장 맵지않은 음식과 두번쨰로 맵지않은 음식을 뽑아낸뒤 
섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)
수식을 실행하여주면 된다.

 

[코드]

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for(int i =0; i<scoville.length; ++i){
            heap.offer(scoville[i]);
        }
        while(heap.peek()<K)    //heap의 원소 값이 K보다 크면 그 이후로는 카운트 안해도됨(우선 순위 큐의 성질)
        {
            if(heap.size()<2)   //모든 음식의 스코빌 지수를 K 이상으로 만들 수 없을 경우
            {                   
                return -1;
            }
            int spicy1 = heap.poll();       //가장 맵지 않은
            int spicy2 = heap.poll();       //두번째로 맵지 않은
            
            int result = spicy1+(spicy2*2);
            
            heap.offer(result);     //다시 heap안으로
            answer++;   //횟수 +1
        }
        
        return answer;
    }
}