[C++] 프로그래머스 '더 맵게' 풀이

문제 설명

매운 것을 좋아하는 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 합니다.

#include <string>
#include <vector>
#include <bits/stdc++.h>

using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0;
    priority_queue<int, vector<int>, greater<int>> pq;
    
    for (int s : scoville) pq.push(s);
    
    while(pq.size()>=2 && pq.top()<K){
        int min1=pq.top(); pq.pop();
        int min2=pq.top(); pq.pop();
        pq.push(min1+min2*2);
        answer++;
    }
    if(pq.top()<K) return -1;
    
    return answer;
}

priority_queue<int, vector<int>, greater<int>> pq;

 

 

heap 까다롭군.. 

아래 글은 지피티한테 첨삭 받은 내용 

 

1. heap이 필요한 이유

스코빌 문제 로직은 이거야.

1. 가장 안 매운 음식 min1 꺼냄
2. 두 번째로 안 매운 음식 min2 꺼냄
3. 새 음식 = min1 + min2 * 2
4. 다시 넣음
5. 모든 음식이 K 이상이 될 때까지 반복

 

즉 매번 필요한 건:

현재 남은 값 중 최솟값

 

이거야.

그런데 매번 sort()를 하면 너무 비효율적이야.

 

sort(scoville.begin(), scoville.end());

 

이걸 반복하면 매번 전체 정렬이라 느려져.

그래서 heap을 쓰면:

최솟값 확인: O(1)
최솟값 꺼내기: O(log N)
새 값 넣기: O(log N)

 

으로 처리할 수 있어.

---

2. C++ heap STL은 두 종류가 있음

C++에서 heap을 쓰는 방법은 크게 두 가지야.

1. priority_queue
2. vector + make_heap / push_heap / pop_heap

 

코테에서는 보통 priority_queue를 추천해.
make_heap 계열은 내부 동작을 직접 다루는 느낌이라 처음엔 더 헷갈려.

---

3. priority_queue로 min heap 만들기

기본 priority_queue<int>는 max heap이야.

 

priority_queue<int> pq;

 

큰 값이 먼저 나와.

 

pq.push(1);
pq.push(5);
pq.push(3);

cout << pq.top(); // 5

 

그런데 스코빌 문제는 작은 값이 먼저 나와야 해. 그래서 이렇게 써.

 

priority_queue<int, vector<int>, greater<int>> pq;

 

이게 min heap이야.

 

priority_queue<int, vector<int>, greater<int>> pq;

pq.push(1);
pq.push(5);
pq.push(3);

cout << pq.top(); // 1

 

---

4. priority_queue 주요 메서드

스코빌 문제에서 필요한 건 딱 이것들뿐이야.

메서드의미

push(x)	값 넣기
top()	현재 최솟값 확인
pop()	현재 최솟값 제거
size()	원소 개수
empty()	비어 있는지 확인

주의할 점:

 

pq.pop();

 

은 값을 반환하지 않아.

그래서 최솟값을 꺼낼 때는 이렇게 해야 해.

 

int min1 = pq.top();
pq.pop();

 

---

5. 스코빌 문제 정답 구조

이 문제는 이 패턴 그대로 외워도 돼.

 

#include <string>
#include <vector>
#include <queue>
#include <bits/stdc++.h>

using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0;

    priority_queue<int, vector<int>, greater<int>> pq;

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

    while (pq.size() >= 2 && pq.top() < K) {
        int min1 = pq.top();
        pq.pop();

        int min2 = pq.top();
        pq.pop();

        int mixed = min1 + min2 * 2;

        pq.push(mixed);
        answer++;
    }

    if (pq.top() < K) {
        return -1;
    }

    return answer;
}

 

---

6. 왜 pq.size() >= 2가 필요해?

두 개를 섞어야 하니까 최소 2개가 있어야 해.

 

while (pq.size() >= 2 && pq.top() < K)

 

이 조건은 이런 뜻이야.

아직 제일 작은 음식이 K보다 작고,
섞을 음식이 최소 2개 이상 있으면 계속 섞는다.

 

만약 음식이 1개만 남았는데도 K보다 작으면 더 이상 섞을 수 없어.

그래서 마지막에 확인해.

 

if (pq.top() < K) return -1;

 

---

7. 네가 쓰려던 make_heap 방식

네가 쓴 건 이 방식이었어.

 

make_heap(scoville.begin(), scoville.end(), greater<int>());

 

이건 vector 자체를 heap 구조로 만드는 거야.

greater<int>()를 넣었으니까 min heap이 돼.

 

make_heap(scoville.begin(), scoville.end(), greater<int>());

 

그러면:

 

scoville.front()

 

에 최솟값이 와.

하지만 여기서 바로 이걸 하면 안 돼.

 

sort_heap(scoville.begin(), scoville.end(), greater<int>());

 

왜냐면 sort_heap은 heap을 유지하는 함수가 아니라, heap을 정렬 배열로 끝내는 함수야.

즉 이 문제처럼 계속 최소값 꺼내고 새 값 넣는 상황에서는 sort_heap이 아니라:

 

pop_heap
push_heap

 

을 써야 해.

---

8. make_heap 계열로 풀면 이렇게 됨

 

#include <string>
#include <vector>
#include <bits/stdc++.h>

using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0;

    make_heap(scoville.begin(), scoville.end(), greater<int>());

    while (scoville.size() >= 2 && scoville.front() < K) {
        pop_heap(scoville.begin(), scoville.end(), greater<int>());
        int min1 = scoville.back();
        scoville.pop_back();

        pop_heap(scoville.begin(), scoville.end(), greater<int>());
        int min2 = scoville.back();
        scoville.pop_back();

        int mixed = min1 + min2 * 2;

        scoville.push_back(mixed);
        push_heap(scoville.begin(), scoville.end(), greater<int>());

        answer++;
    }

    if (scoville.front() < K) {
        return -1;
    }

    return answer;
}

 

근데 솔직히 처음 heap 쓰는 단계에서는 이 방식보다 priority_queue가 훨씬 편해.

---

9. pop_heap이 헷갈리는 이유

이게 제일 중요해.

 

pop_heap(v.begin(), v.end(), greater<int>());

 

이 함수는 최솟값을 바로 삭제하지 않아.

대신:

front에 있던 최솟값을 back으로 이동시킴

 

그래서 반드시 이렇게 써야 해.

 

pop_heap(v.begin(), v.end(), greater<int>());
int minValue = v.back();
v.pop_back();

 

즉 pop_heap 이름만 보면 삭제 같지만, 실제 삭제는 pop_back()이 하는 거야.

---

10. push_heap도 마찬가지

새 값을 heap에 넣을 때도 push_heap이 직접 값을 넣어주지 않아.

먼저 vector에 값을 넣어야 해.

 

v.push_back(mixed);
push_heap(v.begin(), v.end(), greater<int>());

 

순서가 중요해.

 

v.push_back(새값);
push_heap(...);

 

---

11. sort_heap은 언제 쓰는 거냐?

sort_heap은 heap을 다 쓰고 나서 정렬 결과가 필요할 때 써.

예를 들어:

 

vector<int> v = {3, 1, 5, 2};

make_heap(v.begin(), v.end());

sort_heap(v.begin(), v.end());

 

그러면 최종적으로:

1 2 3 5

 

처럼 정렬돼.

하지만 스코빌 문제에서는 정렬된 배열이 필요한 게 아니야.

필요한 건 매번:

최솟값 2개 꺼내기
새 값 넣기

 

이거라서 sort_heap은 쓰면 안 맞아.

---

12. 이 문제에서 외울 heap 패턴

priority_queue 버전

 

priority_queue<int, vector<int>, greater<int>> pq;

for (int x : arr) {
    pq.push(x);
}

while (pq.size() >= 2 && pq.top() < K) {
    int a = pq.top(); pq.pop();
    int b = pq.top(); pq.pop();

    pq.push(a + b * 2);
    answer++;
}

 

이게 스코빌 문제의 핵심 패턴이야.

---

make_heap 버전

 

make_heap(v.begin(), v.end(), greater<int>());

pop_heap(v.begin(), v.end(), greater<int>());
int a = v.back();
v.pop_back();

v.push_back(x);
push_heap(v.begin(), v.end(), greater<int>());

 

이건 나중에 vector를 직접 heap처럼 다뤄야 할 때 보면 돼.

---

결론

이 문제에서는 이걸 쓰는 게 제일 좋음.

 

priority_queue<int, vector<int>, greater<int>> pq;

 

그리고 흐름은:

pq.top()으로 최솟값 확인
pq.pop()으로 제거
pq.push()로 새 스코빌 삽입

 

처음에는 make_heap, pop_heap, push_heap, sort_heap까지 다 외우려고 하지 말고, 코테에서는 일단 priority_queue min heap부터 확실히 잡으면 돼.