●문제

●입출력

문제풀이 : scoville지수가 K보다 낮으면 가장 낮은 경우 낮은음식은
가장낮은 음식 스코빌지수 + (두번째로 낮은 음식 스코빌지수 * 2) 해준값을 해준다
모든 음식의 스코빌지수가 k 이상이 될떄까지 반복 하고 반복한 횟수 count
풀이 알고리즘 : heap / priority_queue 최소힙
푼방법 : 최소힙 트리를 만들고 힙의 루트노드 < K가 될때까지 반복
최소힙에서 .pop()을 두번해주고 answer++ 해주면 결과도출
#include <string>
#include <vector>
#include <queue>
using namespace std;
int solution(vector<int> scoville, int K)
{
int answer = 0;
//최소힙
priority_queue<int, vector<int>, greater<int>> minPQ;
for (int i : scoville)
{
//힙에 추가
minPQ.push(i);
}
//가장 루트노드가 k이상이 될떄까지 반복
while (minPQ.top() < K)
{
//만약 섞을게 2개 미만이면 실패
if (minPQ.size() < 2)
{
return -1;
}
//첫번째 루트노드 지우기
int rootNodeFirst = minPQ.top();
minPQ.pop();
//두번째 루트노드 지우기
int rootNodeSecond = minPQ.top();
minPQ.pop();
//섞은 음식의 스코빌지수 음식 힙에 다시 넣기
minPQ.push(rootNodeFirst + (rootNodeSecond * 2));
//섞은수 증가
answer++;
}
return answer;
}'C++ 프로그래머스 > Heap' 카테고리의 다른 글
| Algorithm - Heap (0) | 2025.08.11 |
|---|
