[백준/BOJ] 11286번: 절댓값 힙 ( 우선순위 큐 ) - C++ 문제 풀이

문제 설명

 

문제 링크: https://www.acmicpc.net/problem/11286

 

풀이

이 문제는 힙 구조의 자료구조에 데이터를 입력하고, 0을 입력받으면 절댓값으로 가장 작은 원소를 출력하는 문제입니다.

 

이 글에선 STL의 우선순위 큐를 이용해서 문제를 풀 생각입니다.

 

우선순위 큐( priority  queue )는 높은 우선순위를 가진 원소가 먼저 출력되도록 하는 자료구조입니다.

여기에선, 절댓값으로 가장 작은 값을 가진 원소가 높은 우선순위를 가진 원소가 될 것입니다.

 

우선순위 큐에 대한 내용은 여기에 정리해 두었습니다.

[C++] 우선 순위 큐 ( Priority Queue ) 사용법

 

우선순위 큐는 데이터를 오름차순 또는 내림차순으로 정렬하여, 최대 값이나 최소 값을 쉽게 구할 수 있습니다.

그런데, 이 문제에서는 일반적인 크고 작음을 비교할 수 없이, 절댓값으로 작은 원소를 출력하도록 했으므로,

사용자 정렬  함수 객체를 사용해야 합니다.

 

이를 구현해 보면, 다음과 같습니다.

typedef long long MTYPE;

// 사용자 비교 함수 객체
struct Compare{
    
    bool operator()( MTYPE A, MTYPE B){
                
        if ( abs(A) == abs(B)){
            return A > B;
        }
        else{
            return abs(A) > abs(B);
        }
    }
};

이 함수 객체는 절댓값이 작은 순으로 정렬하고, 절댓값이 같은 경우 내림차순으로 정렬하는 객체입니다.

 

이 함수 객체를 우선순위 큐에 사용하면, 자동으로 절댓값이 가장 작은 원소가 힙 구조의 꼭대기에 위치하게 됩니다.

이 값을 출력하고, 우선수위 큐에서 제거하면 문제해결입니다.

int main(){
    
    // 우선순위 큐에 사용자 정렬 함수 객체를 사용합니다.
    priority_queue<MTYPE, vector<MTYPE>, Compare> pq;   

    int N;
    cin >> N;
    
    MTYPE x;
    for ( int i = 0; i < N; i++){
        
        cin >> x;

        if ( x != 0){
            pq.push(x); // 우선 순위 큐에 원소 입력
        }
        else{
            
            if ( pq.empty()){	// 원소가 없으면 0 출력
                cout << 0 << endl;
            }
            else{	
                cout << pq.top() << endl;	// 최소값을 출력

                pq.pop();	// 출력하고 난 후, 원소 제거
            }
        }
    }
    
    return 0;
}

 

 

소스 코드

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

typedef long long MTYPE;

// 사용자 비교 함수 객체
struct Compare{
    bool operator()( MTYPE A, MTYPE B){
                
        if ( abs(A) == abs(B)){
            return A > B;
        }
        else{
            return abs(A) > abs(B);
        }
    }
};


int main(){

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    priority_queue<MTYPE, vector<MTYPE>, Compare> pq;   // 우선순위 큐

    int N;
    cin >> N;
    
    MTYPE x;
    for ( int i = 0; i < N; i++){
        
        cin >> x;

        if ( x != 0){
            pq.push(x); // 우선 순위 큐에 원소 입력
        }
        else{
            
            if ( pq.empty()){
                cout << 0 << endl;
            }
            else{
                cout << pq.top() << endl;

                pq.pop();
            }
        }
    }
    
    return 0;
}