scoville 벡터 (얼마나 매운지를 나타내는 값)와 K를 입력받을 때, scoville 벡터의 모든 값이 K 이상이어야 한다. 그럴려면 scoville 벡터를 섞어야 하는데 섞는 방법은
섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)
이다.
최소한으로 섞어서 모든 scoville 벡터의 element가 K이상이 되도록 하는 횟수를 구하는 문제이다.
scoville의 자료구조를 vector가 아닌 priority_queue로 해야 한다. (문제에선 vector로 입력 받는다.)
왜냐하면 섞은 음식의 스코빌 지수
를 scoville에 재정합 해야되는데 벡터에선 그게 쉽지 않다.
그러므로 최소 우선순위 큐를 사용해야 한다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int solution(vector<int> scoville, int K) {
int answer = 0;
priority_queue<ll, vector<ll>, greater<ll>> pq_sco;
// pq_sco에 스코빌 지수 push
for (auto e : scoville)
{
pq_sco.push((ll)e);
}
while(1)
{
// upper k check
if (pq_sco.top()>=K)
break;
// fail check
if (pq_sco.size() < 2)
return -1;
ll small = pq_sco.top();
pq_sco.pop();
ll big = pq_sco.top();
pq_sco.pop();
pq_sco.push(small + big * 2);
answer++;
}
return answer;
}
priority_queue<ll, vector<ll>, greater<ll>> pq;
이 구조를 잘 기억하자. 코딩테스트를 하다가 reference를 보지 못할 수도 있기 때문이다.