[Programmers] 더 맵게 - Java

문제

프로그래머스

 

풀이

우선 순위 큐를 사용해야하는 이유입니다.

- 모든 음식의 스코빌 지수가 K 이상 == 스코빌 지수가 가장 작은 지수가 K이상이면 된다.와 동일(가장 작은 놈만 보면 되지 않을까?)

- 스코빌 지수의 길이가 100만이다. 즉 선형적으로 검색을 하는 것은 시간 초과가 발생하게 된다.

=> 100만개의 데이터 중에서 제일 낮은 스코빌 지수를 log 연산으로 remove, add 연산을 할 수 있는 장점이 있습니다.

 

1. 스코빌 지수를 꺼내서, K이상인지 확인한다.

2. 스코빌 지수가 1개이면서 K이상이 되지 못하면 만들 수 없는 경우라고 생각하면 된다. (answer = -1하고 while문을 나감)

3. 섞는 연산과 횟수 증가를 한다.

 

시간복잡도: 1000000 * log(1000000)

소스코드

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        
        for (int v : scoville) {
            pq.add(v);
        }
        
        int answer = 0;
        
        while (true) {
            //제일 작은 스코빌 지수 꺼내기
            int v = pq.peek();
            
            //K이상인지 확인
            if (v >= K) {
                break;
            }
            
            //스코빌 지수를 K이상으로 만들 수 없을 경우,(지수가 1개이면서 K보다 작을 경우)
            if (pq.size() == 1 && pq.peek() < K) {
                answer = -1;
                break;
            }
            
            //섞기
            int s1 = pq.remove();
            int s2 = pq.remove();
            
            int sum = s1 + (s2 * 2);
            
            pq.add(sum);
            
            answer++;
        }

        return answer;
    }
}