[Java] 프로그래머스 - 더 맵게

모든 음식의 스코빌 지수가 K 이상이 될 때까지, 가장 맵지 않은 음식 2개를 섞는 최소 횟수를 구하는 문제

 

1. 문제 유형

힙, 우선순위 큐, 구현

 

2. 내가 놓친 포인트

처음 떠올린 접근 : 처음에는 Deque를 사용해서 앞에서 음식 2개를 꺼내고, 섞은 값을 다시 앞에 넣는 방식으로 풀었다.

오답 원인: Deque는 입력된 순서대로 값을 관리할 뿐, 최솟값을 자동으로 앞으로 보내주지 않는다.

 

3. 핵심 로직 & 해결 방법

핵심 조건: 매 반복마다 현재 음식 중 가장 작은 값 2개를 꺼내야 한다.

풀이 아이디어:

1. 모든 스코빌 지수를 PriorityQueue에 넣는다.
2. peek()로 현재 가장 작은 값이 K 이상인지 확인한다.
3. K보다 작다면 poll()을 두 번 해서 가장 작은 음식 2개를 꺼낸다.
4. first + second * 2 공식으로 새 음식을 만든다
5. 새 음식을 다시 PriorityQueue에 넣고 횟수를 증가시킨다.
6. 더 이상 섞을 수 없는데도 K 이상을 만들 수 없다면 -1을 반환한다.

4. 구현 코드

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        for (int s : scoville) {
            pq.offer(s);
        }

        int count = 0;

        while (pq.size() >= 2) {
            if (pq.peek() >= K) {
                return count;
            }

            int first = pq.poll();
            int second = pq.poll();

            int mixed = first + second * 2;
            pq.offer(mixed);

            count++;
        }

        return pq.peek() >= K ? count : -1;
    }
}

시간 복잡도: O(N log N) / 공간 복잡도: O(N)

---

 

인사이트

• 문제에서 “가장 작은 값”, “가장 큰 값”, “우선순위가 높은 값”을 반복해서 꺼내야 한다면 PriorityQueue(우선순위 큐)를 먼저 의심해봐야 한다.

 

 

문제 출처 - https://school.programmers.co.kr/learn/courses/30/lessons/42626