[프로그래머스,자바] Level2: 더 맵게

문제분석

목표: 모든 음식을 스코빌 지수 K이상으로 만들기

만드는법 : 가장낮은 음식 스코빌 +(두번째로 낮은 음식 스코빌)*2

 

문제는 정말 쉽다. 공식을 이용하여 모든 음식을 K이상으로만 만들면된다.

하지만, 제한사항을보면 어마어마한 길이의 스코빌이 주어진다.

만약, 별 생각없이 리스트 생성하고 매번 정렬 하면서 최솟값과 2번째 최소값을 구한다면 효율성 오류가난다.

 

문제를 풀기위해선, 가장 낮은 음식과 두번째로 낮은 음식을 섞은뒤 배열에 넣은뒤,

다시 오름차순 정렬해서 낮은 음식과 두번째 음식을 찾아야한다.

 

어찌됏건, 매번 반복할때마다 숫자를 넣고 정렬을 해야한다. 

 

그런데 이 정렬을 매우빠르게 해주는 스마트한 녀석이있는데. 바로 자료구조의 Heap(힙)이다.

자바는 Heap을 응용한 PriorityQueue가 있는데 이걸 사용할것이다.

 

PriorityQueue는 매번 값이들어오면, 자동으로 정렬이된다.

https://taehoung0102.tistory.com/66

자료구조: PriorityQueue(Heap)

 

PriorityQueue의 특징을 살려서 코딩을한다면, 이 문제는 통과하게된다.

문제풀이

import java.util.*;
class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        
        for(int data:scoville){
            pq.add(data);
        }
        
         while(true){
            if(K>pq.peek()){
                pq.add(pq.poll()+pq.poll()*2);
                answer++;
            }
            else{                
                break;
            }               
             if(pq.size()==1&&pq.peek()<K){
                 answer=-1;
                 break;
             }
          }
        return answer;
    }
}