[백준] 1655 가운데를 말해요 (C++)

문제

1655번: 가운데를 말해요 (acmicpc.net)

1655번: 가운데를 말해요

 

풀이

간단하게 문제를 푼다면 입력을 받을 때마다 배열을 정렬하고 그 중앙값을 출력하여 해결할 수 있습니다.
하지만 입력을 받을 때마다 정렬을 하게 되고 0.1초의 시간제한 안에 해결할 수 없습니다.

 

그래서 필요한 방법은 최소 힙, 최대 힙 두 개를 활용하여 관리하는 것입니다.
중앙값을 기준으로 작은 값들은 최대 힙에, 큰 값들은 최소 힙에 넣습니다.
이때 중앙값이 정말 중앙값이기 위해선 최대힙의 크기와 최소힙의 크기가 같거나 차이가 1이어야 합니다.
외친 수가 짝수개라면 중간에 있는 수 중 작은 수를 말하기로 했으므로 두 힙의 크기가 같다면 최대힙의 root를 출력합니다.

 

출력하는 경우의 수를 줄이기 위해 항상 최대힙의 root를 출력하도록 하고 싶습니다.
따라서 최대힙이 항상 최소힙보다 크기가 0 ~ 1 크도록 유지시킵니다.

 

글로 보는 것보다 직접 예시를 보는 것이 이해하기 더 편할거 같으니 문제의 예시를 이용하여 해봅시다.

 

 

 

입력: 1

최대힙 : 1
최소힙 : 
중앙값 : 1

 

입력: 5

최대힙 : 1
최소힙 : 5
중앙값 : 1

 

입력: 2

최대힙 : 1, 2
최소힙 : 5
중앙값 : 2

 

입력: 10

최대힙 : 1, 2
최소힙 : 5, 10
중앙값 : 2

 

입력: - 99

최대힙 : -99, 1, 2
최소힙 : 5, 10
중앙값 : 2

 

입력: 7

최대힙 : -99, 1, 2
최소힙 : 5, 7, 10
중앙값 : 2

 

입력: 5

최대힙 : -99, 1, 2
최소힙 : 5, 5, 7, 10
중앙값 : 2

하지만 이때 최대힙의 크기가 최소힙보다 작아집니다. 우리는 항상 최대힙의 크기가 0 ~ 1 크도록 정했으므로 

최소힙의 root를 최대힙으로 이동시킵니다.

최대힙 : -99, 1, 2, 5
최소힙 : 5, 7, 10
중앙값 : 5

 

 

정리하면 

1. 입력이 중앙값보다 크다면 최소힙, 작다면 최대힙에 삽입

2. 최대힙의 크기가 항상 0 ~ 1 크도록 유지

3. 중앙값은 최대힙의 root 출력

 

 

C++에서는 최대힙, 최소힙을 우선순위 큐로 구현할 수 있습니다.

 

 

코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

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

    int n;
    cin >> n;

    priority_queue<int, vector<int>, greater<int>> minHeap;
    priority_queue<int, vector<int>, less<int>> maxHeap;

    int middle = 10000; // 첫입력이 maxHeap에 들어가도록

    for (int i=0; i<n; ++i)
    {
        int input;
        cin >> input;

        if (middle < input)
        {
            minHeap.push(input);
        }
        else
        {
            maxHeap.push(input);
        }

        // maxHeap.size()가 0~1개 더 많도록 유지
        if (minHeap.size() > maxHeap.size())
        {
            int temp = minHeap.top();
            maxHeap.push(temp);
            minHeap.pop();
        }
        else if(maxHeap.size() - minHeap.size() >= 2) 
        {
            int temp = maxHeap.top();
            minHeap.push(temp);
            maxHeap.pop();
        }

        middle = maxHeap.top();
        cout << maxHeap.top() << "\n";

    }
    return 0;
}