[BOJ알고리즘, C++]#11286_절댓값 힙, 힙, 최소 힙, 최대 힙, 우선순위 큐, priority_queue

 

[BOJ알고리즘, C++]#11286_절댓값 힙

 

BOJ 알고리즘 문제 풀이, 11286번 문제 "절댓값 힙"

C++의 STL이 제공하는 priority_queue 컨테이너를 활용하는 문제

 

---

 

Overview

 

1. 문제
2. 풀이
3. 코드

 

#1. 문제

 

#2. 풀이

1. 힙

[자료구조]#5_트리

 

• [정의] : 힙은 반 정렬 상태를 유지하는 이진트리의 한 종류입니다. 힙은 두 종류로, 최대 힙은 부모 노드가 자식 노드보다 크거나 같고, 최소 힙은 부모 노드가 자식 노드보다 작거나 같은 형태를 유지합니다.

 

2. 우선순위 큐

[자료구조]#7_우선순위 큐

 

• [개념] : 우선순위 큐는 원소들이 우선순위에 따라 정렬된 연결 자료구조입니다. 원소의 삽입/삭제 순서와 무관하게 가장 높은 우선순위를 가진 원소가 먼저 제거되는 특징을 갖고 있습니다. 우선순위 큐는 삽입/제거 작업 시 정렬 작업을 자동적으로 수행합니다. 결과적으로, 우선순위 큐는 내부적으로 항상 정렬된 상태를 유지하는 자료구조입니다.
• [성능] : 우선순위 큐의 삽입/삭제 작업의 평균/최악 시간 복잡도는 O(log n)입니다. 이유는 간단합니다. 우선순위 큐의 삽입/삭제 작업은 매번 정렬 작업을 동반하며, 힙의 정렬 작업에 소요되는 시간이 일반적으로 O(log n) 시간 복잡도를 갖기 때문입니다.
• [단점] : 우선순위 큐는 삽입/삭제 작업 시 매번 정렬 작업을 수행합니다. 따라서, 정렬 작업에 추가적인 메모리 공간이 필요하며, 그 구현이 비교적 복잡합니다. 

 

3. priority_queue 컨테이너

[Basic C++] #69_priority_queue

 

4. priority_queue의 정렬 기준

1. priority_queue 컨테이너는 별도의 비교 함수를 세 번째 인자로 전달하여, 그 정렬 기준을 변경할 수 있습니다.
2. 먼저, 주어진 입력 값을 절댓값과 원본 값을 pair 형식으로 묶어줍니다. 그리고, 별도의 정의 함수를 정의합니다.
3. 사용자 정의 비교 함수는 먼저 pair 형식의 first(절댓값)을 비교하여 절댓값이 적은 pair 항목에게 더 높은 우선순위를 부여합니다. 만약, pair의 first 값이 서로 같다면, 추가적으로 pair의 second 값을 비교해 원본 값이 더 적은 pair 항목에게 높은 우선순위를 부여합니다.

 

#3. 코드

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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int N;
    // pair<절대 값, 원본 값>
    // #1. Compare 함수 객체 : 절대 값 우선 비교, 같다면 원본 값 비교
    auto Compare = [](const pair<int, int> &a, const pair<int, int> &b)
    {
        if (a.first == b.first)
            return a.second > b.second;
        else
            return a.first > b.first;
    };

    // #2. Compare 함수 객체의 정렬 방법에 따른 우선 순위 큐 초기화
    priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(Compare)> pq(Compare);

    cin >> N;

    while (N--)
    {
        int tmp;
        cin >> tmp;

        // #1. tmp 값이 0일 경우, 우선 순위 큐에 새로운 값을 삽입
        if (tmp != 0)
        {
            // pair<절대 값, 원본 값> 형식으로 삽입
            pq.push(make_pair(abs(tmp), tmp));
        }
        // #2. tmp 값이 0이 아닐 경우, "출력"
        else
        {
            // #1. 우선 순위 큐가 비어있지 않을 경우
            if (!pq.empty())
            {
                cout << pq.top().second << '\n';
                pq.pop();
            }
            // #2. 우선 순위 큐가 비어있을 경우
            else
            {
                cout << 0 << '\n';
            }
        }
    }

    return 0;
}