문제는 HEAP으로 풀이하라 했는데, 우선순위 큐로 풀었다. -> 힙은 트리 기반의 완전 이진 트리를 이용한 우선순위 큐 구현에 사용된다.
힙 HEAP
힙은 완전 이진 트리(Complete Binary Tree)의 일종으로, 부모 노드와 자식 노드 간의 값의 관계를 이용하여 효율적인 데이터 처리와 우선순위 관리가 가능하다.
힙에는 최소 힙(min heap), 최대 힙(max heap)이 존재한다.
최소 힙
- 부모 노드의 값이 항상 자식 노드보다 작거나
- 트리의 루트에는 가장 작은 값이 위치함
최대 힙
- 부모 노드의 값이 항상 자식 노드보다 크거나 같다는 규칙
- 트리의 루트에는 가장 큰 값이 위치함
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int solution(vector<int> scoville, int K) {
int answer = 0;
int i, first_lowest, second_lowest, next, count = 0;
priority_queue<int, vector<int>, greater<int>> pq;
//섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)
for(int temp : scoville){
pq.push(temp);
}
while(pq.top() < K && pq.size() >= 2){
first_lowest = pq.top();
pq.pop();
second_lowest = pq.top();
pq.pop();
next = first_lowest + (second_lowest * 2);
pq.push(next);
cout << first_lowest << " + " << "(" << second_lowest << " * 2) = "<< "next : " << next << "\n";
count++;
}
if(pq.size() == 1 && pq.top() < K){
answer = -1;
}
else{
answer = count;
}
return answer;
}#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int solution(vector<int> scoville, int K) {
int answer = 0;
int i, first_lowest, second_lowest, next, count = 0;
priority_queue<int, vector<int>, greater<int>> pq;
//섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)
for(int temp : scoville){
pq.push(temp);
}
while(pq.top() < K && pq.size() >= 2){
first_lowest = pq.top();
pq.pop();
second_lowest = pq.top();
pq.pop();
next = first_lowest + (second_lowest * 2);
pq.push(next);
cout << first_lowest << " + " << "(" << second_lowest << " * 2) = "<< "next : " << next << "\n";
count++;
}
if(pq.size() == 1 && pq.top() < K){
answer = -1;
}
else{
answer = count;
}
return answer;
}