[프로그래머스] 더 맵게

프로그래머스 <더 맵게>

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

코딩테스트 연습 - 더 맵게

---

<더 맵게>

음식의 스코빌 지수를 담고 있는 scoville 배열이 주어졌을 때 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 최소 몇 번 음식을 섞어야 하는지 구하여라.

 

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두번째로 맵지 않은 음식의 스코빌 지수 * 2)

---

문제 해결

이 문제에서 사용하는 연산을 보면 가장 맵지 않은 음식과 두번째로 맵지 않은 음식의 스코빌 지수가 필요하고 섞은 음식의 스코빌 지수도 나중에 연산에 필요하기 때문에 우선순위 큐를 사용한다.

 

먼저 scoville 배열에 있는 값을 우선순위 큐에 넣어준다.

 

0. answer = 0

1. 우선순위 큐에서 값 A를 하나 꺼낸다.

2. 우선순위 큐가 비지 않았고 꺼낸 값이 K보다 작다면 또 우선순위 큐에서 값 B를 하나 꺼낸다.

3. answer에 +1을 한다. 섞은 음식의 스코빌 지수를 구하고 이 값을 우선순위 큐에 넣는다. A + (B*2)

2, 3번을 계속 반복한다.

반복은 값 A가 K보다 크거나 같은 경우, A를 꺼낸 후 우선순위 큐가 빈 경우에 종료된다.

 

값 A가 K보다 크거나 같은 경우는 가장 작은 값인 값 A가 K보다 크거나 같기 때문에 모든 음식의 스코빌 지수가 K 이상인 경우이다.

값 A를 꺼낸 후 우선순위 큐가 빈 경우는 값 A가 K보다 작은데 섞을 음식이 없는 경우이기 때문에 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우이다. 따라서 이때는 answer = -1이다.

---

코드

import java.util.PriorityQueue;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        PriorityQueue<Integer> q = new PriorityQueue<>();
        int len = scoville.length;
        for(int i = 0; i < len; i++){
            q.add(scoville[i]);
        }
        
        while(true){
            int pop = q.poll();
            if(pop >= K){
                break;
            }
            if(q.size() == 0){
                if(pop < K){
                    answer = -1;
                }
                break;
            }
            int omPop = q.poll();
            answer++;
            q.add(pop + omPop*2);
        }
        
        return answer;
        
    }
}

---

결과

---