[ C++/cpp ] 백준 (11268 절댓값 힙) ⭐자료구조, 우선순위 큐

 

백준 11268번 절댓값 힙

( 실버 1 )

 

https://www.acmicpc.net/problem/11286

11286번: 절댓값 힙

 

 

(정답 코드)

#include <iostream>
#include <queue>

using namespace std;

struct cmp {
    bool operator() (const int& x1, const int& x2) {
        if(abs(x1) != abs(x2)) {
            //절댓값 다른경우 절댓값이 작은 수에 우선순위 부여
            return abs(x1) > abs(x2);
        }
        
        // 절댓값 같으면 작은 수에 우선순위 부여
        return x1 > x2;
    }
};

int main()
{
    
    ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
    
    int n , x ;
    priority_queue <int, vector<int>, cmp> pq; //절댓값 힙 구현할 우선순위 큐
    
    cin >> n;
    
    
    while(n--) {
        cin >> x;
        
        if(x) {
            pq.push(x);
        } 
        
        else {
            
            //pq가 비어있는 경우 0 출력
			if (pq.empty()) { 
				cout << "0\n";
			}
			else {
				cout << pq.top() << "\n";
				pq.pop();
			}
        }
    }
    
    return 0;
}

 

 

📖 풀이 요약

이 문제는 우선순위 큐를 다루는 문제이다 !

우선순위 큐와 힙 자료구조에 대해 더 알고싶다면, 아래 링크로 :)

 

https://somde.tistory.com/176

[ 우선순위 큐와 힙 ] 완전 이진 트리, heap의 구현 ( + 백준 11279번 최대힙)

 

 

 

 

🚨 항상 우선순위 큐 문제에서 힙을 쓸 때, 유의할 점 !!

" 비어있는 큐의 top을 접근하진 않았는지 !! " 체크 해야한다.

 

 

위의 문제는 힙 자료구조를 기반으로, 원하는 힙의 조건에 따라 구조체를 구현해 풀 수 있다 !

// 마치 sort 비교함수처럼, 구조체를 선언해서 원하는 힙의 조건을 명시할 수 있다 ! :)

// 절댓값을 비교하여 최대 힙으로 만드는 비교자 구조체
struct CompareAbs {
    bool operator()(int a, int b) const {
        return abs(a) > abs(b);
    }
};

// 최대힙
    priority_queue<int> maxHeap;

    // 최소힙
    priority_queue<int, vector<int>, greater<int>> minHeap;

    // 절댓값 힙
    priority_queue<int, vector<int>, CompareAbs> absHeap;