백준 1655 가운데를 말해요(c++)

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

1655번: 가운데를 말해요

이 문제는 최대힙(priority_queue), 최소힙(priority_queue<int, vector<int>, greater<int>>)를 이용하여 풀 수 있습니다. 힙이 무엇인지 설명드리겠습니다.

 

힙의 특성에 대해 설명드리겠습니다.

 

최대힙은 부모 노드는 자식 노드에 들어있는 값보다 커야하고, 최소힙은 부모 노드는 자식 노드에 들어있는 값보다 작아야 합니다.

힙은 완전 이진 트리(Complete Binary Tree)이기 때문에, N개의 힙에 들어가있으면 높이는 LogN입니다.

최대 힙의 연산 과정은 주어진 값에서 부모 > 자식 인지 비교 -> 그렇지 않으면 change한다. -> Maxheap 충족

 

최대 힙 특정 값 제거 과정은  최대 힙 제거는 루트를 가장 마지막에 있는 값으로 바꾸고, 자식들과 비교해 값을 change 합니다.

 

문제의 솔루션

 

1.왼쪽 오른쪽 N/2 , N/2로 나눠준다

2.홀수인 경우 홀수 (왼 == 오 + 1) 개수 L>=R (크기)

3.왼쪽에 있는 수 <= 오른쪽에 있는 수(L.value <= R.value)

4. 최종적으로 L(최대 힙)의 가장 큰 값이 중간 값이 됩니다. 왜냐하면 3번 조건 때문에 중간값을 만족할 수 있게 됩니다.

 

<코드>

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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n;
    cin >> n;

    priority_queue<int> l;
    // 최대 힙
    priority_queue<int, vector<int>, greater<int>> r;
    // 최소 힙

    while (n--)
    {
        int x;
        cin >> x;

        if (l.empty() || r.empty())
        {
            l.push(x);
        }
        // 문제 조건에서 왼쪽 힙의 크기가 오른쪽 힙의 크기보다 커야함.
        else
        {
            if (x <= l.top())
            {
                l.push(x);
            }
            else if (x >= r.top())
            {
                r.push(x);
            }
            else
            {
                l.push(x);
            }
        }
        while (!(l.size() == r.size() || l.size() == r.size() + 1))
        {
            if (l.size() > r.size())
            {
                r.push(l.top());
                l.pop();
                // 왼 > 오  오른쪽에 왼쪽꺼 push, 왼쪽 pop
            }
            else
            {
                // 왼쪽에 오른쪽꺼 push, 오른쪽 pop
                l.push(r.top());
                r.pop();
            }
        }
        cout << l.top() << '\n';
        // 왼쪽에서 가장 큰 값이 가운데 의미
    }
}