들어가는 말
스코빌 지수가 들어있는 배열을 받아서 제일 작은 스코빌 지수와 두 번째로 작은 스코빌 지수를 이용해 모든 수가 K보다 크게 만드는 문제다.
힙을 이용해 푸는 문제다. 힙은 정렬된 이진수 트리로 부모 노드의 value가 자식 노드보다 크거나 같은 최대 힙과 부모 노드의 value가 자식 노드보다 작거나 같은 최소 힙이 있다. 이는 우선순위 큐로 이용할 수 있다.
처음에는 스텍으로도 풀 수 있지 않을까? 생각했지만 스텍으로 풀 경우 새로운 값을 넣어주면 계속 정렬을 해줘야 해서 우선순위 큐로 풀었다. 사실 이렇게 빨리 풀 줄은 몰랐다. 그냥 전체적으로 이렇게 돌아가면 되지 않을까 싶어서 코드를 짰는데 그게 맞아 떨어졌다. 정확하게 100%는 아니고 한 85%는? 자꾸 틀리는 문제는 배열의 길이가 1이거나 전부 다 합했을 때조차 K를 넘지 못하는 경우를 추가해줘서 풀었다. 참고로 이때는 answer이 -1이었다. 문제에 써 있었는데 이걸 못 봤다니. 이해했다고 넘어가지 말고 제한 사항을 꼼꼼하게 읽자...
코드 설명
일단 우선순위 큐를 만들어 스코빌 지수를 넣어줬다. 이때 중요한 점은 제일 작은 스코빌 지수와 그 다음으로 작은 스코빌 지수를 가져오기 위해 내림차순이 아니라 오름차순으로 넣어야 한다는 거다. 그리고 pq가 빌 때까지 while문을 돌려주는 데 만일 pq의 top이 K보다 작을 경우 새로운 스코빌 지수를 만들어준다. 제일 작은 스코빌 지수를 first에 넣고 pop을 해준다. 그리고 그 다음으로 작은 스코빌 지수를 second에 넣고 pop을 해준다. 그리고 주어진 식에 따라 new_sc를 만들면 된다.
여기서 주의할 점은 스코빌 지수 벡터의 길이가 1이거나 모든 스코빌 지수를 계산했는데도 K보다 작은 경우다. 이때는 answer에 -1을 넣어서 리턴하면 된다(-1을 리턴하라는 건 문제에 써 있었다. 문제를 잘 읽자).
만일 위의 주의점에 헤당하지 않으면 pq에다가 new_sc를 넣어주고 answer++를 해주면 된다. pq자체가 오름차순으로 된 우선순위 큐이기 때문에 따로 정렬을 할 필요는 없다.
만일 pq의 top이 K보다 큰 경우에는 그냥 answer을 리턴하면 된다. pq는 오름차순으로 정렬이 되어 있기 때문에 top에 있는 숫자가 K보다 크면 뒤의 숫자도 자동으로 K보다 크기 때문이다.
코드
#include <string>
#include <vector>
#include <queue>
using namespace std;
int solution(vector<int> scoville, int K) {
int answer = 0;
int first = 0;
int second = 0;
int new_sc = 0;
/*우선순위 큐, 오름차순으로 맨 뒤에 거 두 개*/
priority_queue<int, vector<int>, greater<int>> pq;
for(auto sc : scoville){
pq.push(sc);
}
while(!pq.empty()){
if(pq.top() < K){
first = pq.top();
pq.pop();
second = pq.top();
pq.pop();
new_sc = first + (second*2);
if(new_sc < K && pq.empty()){
answer = -1;
return answer;
}
pq.push(new_sc);
answer++;
}else{
return answer;
}
}
}