더 맵게

문제정의

---

모든 음식이 스코빌 지수 k를 넘기게 하기 위해 맵지 않은 음식을 섞어서 더 맵게 만들려고 한다.

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

모든 음식을 K이상의 스코빌 지수로 만들려고 할 때 섞어야 하는 최소 횟수를 계산하는 문제이다. 만약 불가능하다면 -1을 반환한다.

문제풀이

---

전체 코드는 다음과 같다.

import java.util.*;

public class MoreSpicy {

    //프로그래머스 level2 문제풀이 더 맵게

    public static void main(String[] args) {
        int[] scoville = {1, 2, 3, 9, 10, 12};
        int K = 7;
        int answer = 0;
        boolean isPossible = true;
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for(int food : scoville)
            pq.add(food);
        while(pq.size() > 1)
        {
            if(pq.peek() >= K)
            {
                isPossible = true;
                break;
            }
            else
            {
                Integer food1 = pq.poll();
                Integer food2 = pq.poll();
                pq.add(food1 + food2*2);
                answer++;
            }
            
        }
        if(pq.peek() < K)
            answer = -1;
        System.out.println(answer);
    }
    
}

이 문제는 우선순위 큐만 알면 쉽게 해결할 수 있다. 일단 모든 음식을 큐에 넣은 다음 맨 앞 음식을 확인하여 K미만 이라면 큐에서 두 음식을 꺼내 계산식에 넣은 결과를 다시 넣는다. 만약 가장 안 매운 음식이 K를 넘는다면 반복문을 탈출하고 else문에 들어간 횟수를 반환한다. 만약 모든 음식을 섞어도 스코빌 지수를 만족하지 못한다면 큐에는 하나의 음식만 남게 되고 while문 조건에 의해 반복문을 탈출한다. 큐에서 가장 안 매운 음식을 꺼냈을 때 K보다 작으므로 -1이 된다. 만약 모든 음식이 K를 넘는다면 answer은 0이 될 것이다.

우선순위 큐를 활용했으므로 최종 시간복잡도는 \(O(nlogn)\)이다.

테스트

질문하기를 둘러보니 직접 힙을 구현한 경우 통과가 안되고 라이브러리 힙을 사용해야 통과되는 경우가 더러 있었다고 한다. 이 부분에서는 효율성 평가 개선이 이루어져야 한다고 생각한다.