[프로그래머스] 힙(Heap) - 더 맵게 / 우선순위큐(priority_queue)

문제

 

풀이

#include <string>
#include <vector>
#include <queue> //heap 구현
#include <functional>// greater

using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0;
    priority_queue<int, vector<int>, greater<int>> pq;
    for(int i =0; i < scoville.size(); i++){
        pq.push(scoville[i]);
    }
    
    while(pq.top() < K){
        if(pq.size() <= 1) return -1;
        int n = pq.top(); pq.pop();
        pq.push(n + pq.top() * 2 ); pq.pop();
        answer ++;
    }
    
    return answer;
}

 

 

heap을 사용한 이유

답을 얻기 위해선 배열의 최솟값이 K이상이 될 때까지 반복문을 돌려야 하고, 그때마다 최솟값을 확인해야 하는데

힙을 사용하면 최댓값 또는 최솟값을 찾기 수월하기 때문이다. 또한 코드의 의도도 확실해진다!

 

힙(heap)

최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진트리를 기본으로 한 자료구조

• A가 B의 부모 노드이면, A의 키값과 B의 키값 사이에는 대소 관계가 성립한다.
• 힙에는 두 가지 종류가 있으며, 부모 노드의 키값이 자식 노드의 키값보다 항상 큰 힙을 '최대 힙(Max Heap)', 부모 노드의 키값이 자식 노드의 키값보다 항상 작은 힙을 '최소 힙(Min Heap)'이라고 부른다.

Max Heap / 출처 : 위키백과

• 키값의 대소 관계는 오로지 부모 노드와 자식 노드 간에만 성립하며, 형제 사이에는 대소 관계가 정해지지 않는다.
• 이러한 규칙을 유지하며 원소의 추가/제거 과정을 거치면 루트 노드(부모 노드가 존재하지 않는 최상위 노드.)에 있는 원소 값은 Min Heap에서는 최솟값이, Max Heap에서는 최댓값이 된다.
• 원소의 추가/제거하는 과정이 O(logN)의 복잡도를 갖고 조회는 O(1)으로 효율적인 구조이다.

 

우선순위 큐

priority_queue<자료형, 구현체, 비교연산자> 

Heap 자료구조 롤 응용한 대표적인 사례가 Priority queue(우선순위 큐)이다.

비교 연산자에는 less<자료형>과 greater<자료형>이 있으며. less는 큰 순서대로, greater은 작은 순서대로 출력된다.

(sort에선 less<>는 오름차순으로, greater <>는 역순으로 정렬한다.)

• 우선순위 큐는 우선순위를 순차적으로 가져올 수 있는 push/ pop이 가능한 자료로 꼭 Heap으로 구현할 필요는 없지만 Heap으로 구현하는 것이 시간 복잡도 면에서 큰 효율을 낼 수 있기 때문에 주로 Heap으로 구현한다. 
• 우선순위 큐는 기본적으로 Max Heap, 즉 원소를 pop 하면 큰 수부터 내림차순으로 된다. 오름차순으로 하고 싶은 경우에는 원소에 전체적으로 음수를 취해주거나 우선순위 큐를 선언함에 있어 인자를 넣어 Min Heap을 만들어 주면 된다.

#include <iostream>
#include <queue>
using namespace std;

int main() {
	queue<int> qu;
	qu.push(1);
	qu.push(9);
	qu.push(5);
	int sz = qu.size();
	for(int i=0;i<sz;i++){
		cout << qu.front() << ',';
		qu.pop();
	}cout << '\n';
	
	priority_queue<int> p_qu_l;
	p_qu_l.push(1);
	p_qu_l.push(9);
	p_qu_l.push(5);
	sz = p_qu_l.size();
	for(int i=0;i<sz;i++){
		cout << p_qu_l.top() << ',';
		p_qu_l.pop();
	}cout << '\n';
	
	priority_queue<int, vector<int>, greater<int>> p_qu_g;
	p_qu_g.push(1);
	p_qu_g.push(9);
	p_qu_g.push(5);
	sz = p_qu_g.size();
	for(int i=0;i<sz;i++){
		cout << p_qu_g.top() << ',';
		p_qu_g.pop();
	}cout << '\n';
	
	return 0;
}

순서대로

1, 9, 5

9, 5, 1

1, 5, 9 

를 출력한다.

 

우선순위 큐 멤버함수

멤버함수	기능
push()	우선순위 큐에 원소를 추가한다
pop()	우선순위 큐에서 top의 원소를 제거한다
top()	우선순위 큐에서 top에 있는 원소 즉 우선순위가 높은 원소를 반환한다.
empty()	우선순위 큐가 비어있으면 true를 반환하고 그렇지 않으면 false를 반환한다
size()	우선순위 큐에 포함되어 있는 원소의 수를 반환한다

 

---

다른 사람 풀이

#include <vector>
#include <queue>

using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0;
    int needHot;
    priority_queue<int,vector<int>,greater<int>> pq (scoville.begin(),scoville.end());

    while(pq.top()<K) {
        if(pq.size()==1) return answer = -1;
        needHot=pq.top(); pq.pop();
        pq.push(needHot+pq.top()*2);
        pq.pop(); answer++;
    }

    return answer;
}

priority_queue <int, vector<int>, greater<int> pq (scoville.begin(), scoville.end()); 문을 사용하여 벡터 값을 우선순위 큐에 넣을 수 있었다!

 

 

---

https://doorrock.tistory.com/13

[코테를 위한 압축 개념] C++ STL 힙(Heap), 우선순위 큐(Priority queue)

https://ko.wikipedia.org/wiki/%ED%9E%99_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0) 

힙 (자료 구조) - 위키백과, 우리 모두의 백과사전

https://yoon90.tistory.com/12

[C++] priority_queue