[백준/C,C++] 1655번: 가운데를 말해요

www.acmicpc.net/problem/1655

1655번: 가운데를 말해요

풀이

생각보다 꽤 어려웠던 문제입니다.

 

우선순위 큐 2개를 써서 해결할 수 있는 문제인데

 

핵심은 이렇습니다.

 

우선 내림차순의 우선순위 큐(pqMin)와 오름차순의 우선순위 큐(pqMax)를 준비합니다.

 

pqMin에는 중간값보다 작은 값들을 담고, pqMax에는 중간값보다 큰 값들을 담습니다.

 

이때, pqMin을 pqMax의 사이즈와 같거나 1만큼 크게 유지하면,

 

pqMin의 top()은 항상 가운데 값을 유지하고 있게 됩니다.

 

 

예제를 기준으로 설명드리겠습니다.

 

7

1

5

2

10

-99

7

5

 

정수	1	5	2	10	-99	7	5
pqMin	1	1	2, 1	2, 1	2, 1, -99	2, 1, -99	5, 2, 1, -99
pqMax		5	5	5, 10	5, 10	5, 7, 10	5, 7, 10
pqMin.top()	1	1	2	2	2	2	5

한가지 유의해야 할 점은 pqMin의 사이즈를 항상 pqMax의 사이즈와 같거나 1만큼 크게 유지해야 하기 때문에,

 

pqMin, pqMax가 필요 이상으로 사이즈가 커졌을 때, top의 원소를 이동 시켜줘야 한다는 것입니다.

 

#include<iostream>
#include<queue>

using namespace std;

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

    priority_queue<int, vector<int>, greater<int>> pqMax;
    priority_queue<int> pqMin;

    int n; cin >> n;

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

        if (pqMin.empty() || pqMin.top() >= i) {
            pqMin.push(i);
            if (pqMin.size() > pqMax.size() + 1) {
                pqMax.push(pqMin.top());
                pqMin.pop();
            }
        }
        else if (pqMax.empty() || pqMax.top() <= i) {
            pqMax.push(i);
            if (pqMax.size() > pqMin.size()) {
                pqMin.push(pqMax.top());
                pqMax.pop();
            }
        }
        else {
            if (pqMin.size() <= pqMax.size()) pqMin.push(i);
            else pqMax.push(i);
        }

        cout << pqMin.top() << '\n';
    }

    return 0;
}

반례

Input

10
999
1234
5
1
-51
-688
51
0
2347
9999

Output

999

999

999

5

5

1

5

1

5

5