[프로그래머스] 더 맵게

문제

---

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

프로그래머스

 

문제 분석

---

[제한 사항]

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

음식들의 시코빌 지수 가 주어졌을 때 주어진 음식들을 섞어 모든 음식의 스코빌 지수가 K 이상이 되도록 하는 문제이다.

가장 맵지 않은 음식과 두 번째로 맵지 않은 음식을 섞어

(가장 맵지 않은 음식의 스코빌 지수 + 두 번째로 맵지 않은 음식의 스코빌 지수 *2) 의 스코빌을 갖는 음식을 만들어 낼 수 있다.

 

scoville 배열의 길이가 최대 10^6 이기 때문에 O(n) 의 시간 복잡도로 문제를 풀어야 한다.

즉 scoville 배열 안에서 다시 scoville 배열이 반복되면 안된다.

 

문제 접근

---

이 문제는 주어진 스코빌 중 가장 작은 2개를 항상 꺼내서 새로운 음식을 만들어주어야 한다.

그렇기 때문에 우선순위 큐를 사용하면 문제를 쉽게 해결할 수 있다.

 

모든 음식들을 우선순위 큐에 넣어주고 큐에 들어간 모든 음식들이 K 보다 커질 때 까지 우선순위 큐에서 음식 2개를 빼 섞어서 다시 우선순위 큐에 넣어주면 된다.

 

만약 우선순위 큐의 크기가 1이 된다면 반복을 멈추고 마지막 남은 음식의 스코빌 지수가 K보다 작다면 -1을 리턴한다.

 

코드

---

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        
        for(int s : scoville){
            pq.offer(s);
        }
        
        while(pq.peek() < K && pq.size()>=2){
            int small = pq.poll();
            int big = pq.poll();
            
            int mix = small + big * 2;
            pq.offer(mix);
            answer++;
        }
        
        if(pq.peek() < K){
            return -1;
        }
        return answer;
    }
}