> For the complete documentation index, see [llms.txt](https://devlee.gitbook.io/docs/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://devlee.gitbook.io/docs/study/99/99-9-til.md).

# \[99클럽 코테 스터디 9일차 TIL]  프로그래머스 - 더 맵게

## \[level 2] 더 맵게 - 42626

[문제 링크](https://school.programmers.co.kr/learn/courses/30/lessons/42626?language=java)

#### 문제 설명

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

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

Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.\
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

**제한 사항**

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

**입출력 예**

| scoville              | K | return |
| --------------------- | - | ------ |
| \[1, 2, 3, 9, 10, 12] | 7 | 2      |

**입출력 예 설명**

1. 스코빌 지수가 1인 음식과 2인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.\
   새로운 음식의 스코빌 지수 = 1 + (2 \* 2) = 5\
   가진 음식의 스코빌 지수 = \[5, 3, 9, 10, 12]
2. 스코빌 지수가 3인 음식과 5인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.\
   새로운 음식의 스코빌 지수 = 3 + (5 \* 2) = 13\
   가진 음식의 스코빌 지수 = \[13, 9, 10, 12]

모든 음식의 스코빌 지수가 7 이상이 되었고 이때 섞은 횟수는 2회입니다.

***

## 풀이 코드

```java
import java.util.PriorityQueue;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int s : scoville) pq.offer(s);
        // 가장 낮은 수가 K보다 크면 모든 음식의 스코빌 지수가 K보다 크기 때문에 섞을 필요가 없다.
        if (pq.peek() >= K) return answer;
        // 큐에 저장된 데이터가 2개 이상이어야 섞을 수 있다.
        // 가장 낮은 수를 꺼냈을 때 K 이상이면 더 반복할 필요가 없다.
        while (pq.size() > 1 && pq.peek() < K) {
            pq.offer(pq.poll() + 2 * pq.poll());
            answer++;
        }
        // 큐의 가장 낮은 수가 K보다 작으면 -1 을 반환한다.
        return pq.peek() >= K ? answer : -1;
    }
}
```

* Time: 1517.57 ms
* Memory: 123 MB

우선순위 큐(`PriorityQueue`)를 활용하면 쉽게 풀 수 있는 문제이다. 우선순위 큐는 FIFO(선입선출)인 일반적인 큐와 다르게 우선순위가 높은 데이터가 먼저 나간다. 위 풀이에서 우선순위가 높은 데이터는 스코빌 지수가 가장 낮은 수이다.

***

## 돌아보기

막혔던 부분은 두 음식을 섞고 나온 스코빌 지수가 K 이상이면 바로 섞은 횟수를 반환하도록 했던 부분이었다. 예를 들어 아래와 같은 테스트 케이스가 있다면:

* scoville: \[1, 1, 2, 3]
* K: 3

1. 1 + 1 \* 2 = 3, scoville: \[2, 3, 3]
2. 2 + 3 \* 2 = 8, scoville: \[3, 8]

섞은 횟수는 2가 나와야하는데 1번 과정에서 연산 결과 값이 K 이상이기 때문에 바로 섞은 횟수 1을 반환하면서 계속 틀렸다.

### 다음에는

* 문제 **좀 제발** 꼼꼼히 읽기

***

\#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://devlee.gitbook.io/docs/study/99/99-9-til.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.