[프로그래머스] Lv2. 더 맵게

https://school.programmers.co.kr/learn/courses/30/lessons/42626#

프로그래머스

 

일일히 반복문 돌면서  찾기에는 시간복잡도가 너무 크다고 판단

우선순위 큐를 사용해주었다. 왜? 정렬하는데 log N이 걸리기 때문에!

 

예외 상황을 고려해 주어야한다.

input: [7], k:7 인 상황에서 output은 0이 나와야 한다.

 

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        
        for(int value: scoville) {
            pq.add(value);
        }
        
        boolean flag = true;
        
        while(!pq.isEmpty()) {
            
            if(pq.size() == 1 && pq.peek() < K) {
                flag = false;
                break;
            }
         
            int first = pq.poll();
            
            if(first < K) {
                int second = pq.poll();
                int sum = (int)(first + second * 2);
                pq.add(sum);
                answer++;
                
                continue;
            }
            
            break;
        }
        
        if(!flag) {
            answer = -1;
        }
        
        return answer;
    }
}

 

실행 결과