[BOJ알고리즘, C++]#1655_가운데를 말해요, 우선순위 큐, 최소 힙, 최대 힙

 

[BOJ알고리즘, C++]#1655_가운데를 말해요

 

BOJ 알고리즘 문제 풀이, 1655번 문제 "가운데를 말해요"

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

 

---

 

 

Overview

 

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

 

#1. 문제

 

#2. 풀이

1. 우선순위 큐

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

 

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

 

2. priority_queue

[Basic C++] #69_priority_queue

 

• C++의 STL에서 제공하는 priority_queue를 제공합니다.

 

3. 2개의 priority_queue 활용

1. 문제를 풀이하기 위해 두 개의 priority_queue 컨테이너를 활용합니다. 먼저, 최소 값이 가장 높은 우선순위를 갖는 우선순위 큐(최소 힙)와 최대 값이 가장 높은 우선순위를 갖는 우선순위 큐(최대 힙)를 선언합니다.
2. 먼저, 최소 힙과 최대 힙의 크기를 비교하며 그 균형을 유지합니다. 따라서, 입력 값을 우선적으로 최대 힙에 삽입하고, 최대 힙의 크기가 최소 힙의 크기보다 크면 입력 값을 최소 힙에 삽입합니다.
3. 마지막으로, 외친 숫자가 짝수 개일 경우, 작은 수를 골라야 하기 때문에, 최소 힙과 최대 힙 사이즈를 비교하고 최대 힙이 더 클 경우, 최대 힙의 루트 값과 최소 힙의 루트 값을 교환해 줍니다.

 

#3. 코드

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

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    
    int N;
    cin >> N;
    
    // priority_queue를 활용해 최소 힙, 최대 힙 선언
    priority_queue<int, vector<int>, greater<int>> minHeap;
    priority_queue<int, vector<int>, less<int>> maxHeap;
    
    while(N--)
    {
        int tmp;
        cin >> tmp;
        
        if(maxHeap.size() > minHeap.size())
            minHeap.push(tmp);
        else
            maxHeap.push(tmp);
        
        if(!minHeap.empty() && maxHeap.top() > minHeap.top())
        {
            int minRoot = minHeap.top();
            int maxRoot = maxHeap.top();
            
            minHeap.pop();
            maxHeap.pop();
            
            minHeap.push(maxRoot);
            maxHeap.push(minRoot);
        }
        cout << maxHeap.top() << '\n';
    }
    
    return 0;
}