알고리즘/프로그래머스
[프로그래머스][힙][C++] 더 맵게
Min:D
2020. 10. 28. 20:30
문제
프로그래머스 힙 - 더 맵게 (Level 2)
코딩테스트 연습 - 더 맵게
매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같
programmers.co.kr
문제 풀이
접근 방식
아래와 같은 방법으로 새로운 음식을 만들 때,
모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 구하는 문제이다.

가장 작은 값과 두 번째로 작은 값을 지속적으로 구해야하는 문제이기 때문에,
우선순위 큐를 사용하여 min heap을 구현해주었다.
우선순위 큐에 모든 음식의 스코빌 지수를 넣어준 후,
우선순위 큐의 top에 있는 값(최솟값)이 K 이상일 때까지 위의 계산식을 사용하여 음식을 섞어주었다.
우선순위 큐의 사이즈가 1일 때는 더 이상 음식을 섞을 수 없는 상황이므로 -1을 리턴해주도록 구현하였다.
풀이 코드 - C++
#include <string>
#include <vector>
#include <queue>
#include <functional>
using namespace std;
int solution(vector<int> scoville, int K) {
int answer = 0;
priority_queue<int, vector<int>, greater<int> > pq;
for(int i: scoville)
pq.push(i);
while(true) {
if(pq.top() >= K)
return answer;
if(pq.size() == 1)
return -1;
int a = pq.top(); pq.pop();
int b = pq.top(); pq.pop();
pq.push(a+b*2);
answer++;
}
}
실행 결과
