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

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

풀이

우선순위 큐 두 개를 활용해서 해결할 수 있다.

최대 힙과 최소 힙 두 종류를 각각 만들고, 각각 '작은 수'와 '큰 수'를 저장한다. (두 힙의 이름은 각각 small, big라고 하자.)

현재 들어오는 수가 big의 top보다 작거나 같으면 small로 보내고, 아니면 big으로 보낸다.

그리고 두 우선순위 큐의 크기(균형)을 맞춰준다. 항상 두 큐의 크기가 같거나, 아니면 small이 하나 더 크게 만들 수 있다.

그러면 각 단계에서 small의 top이 정답이 된다.

 

이게 무슨 소리냐면,

예제 1, 5, 2, 10, -99, 7, 5를 예를 들어보자.

 

1이 들어왔을 때는 다음과 같다.

 

small 1

big

(답: 1)

 

5가 들어오면,

 

small 1

big 5

(답: 1)

 

2가 들어오면,

 

small 2 1

big 5

(답: 2)

 

10이 들어오면,

 

small 2 1

big 5 10

(답: 2)

 

-99가 들어오면,

 

small 2 1  -99

big 5 10

(답: 2)

 

7이 들어오면,

 

small 2 1 -99

big 5 7 10

(답: 2)

 

5가 들어오면,

small 5 2 1 -99

big 5 7 10

(답: 5)

 

 

 

예제가 좋지 않다. 이번에는 1, 2, 3를 예제로 들어보자.

1이 들어오면

 

small 1

big 

(답: 1)

 

2가 들어오면

 

small 1

big 2

(답: 1)

 

3이 들어오면

small 1

big 2 3

 

여기서 문제가 생긴다! big이 small보다 더 크다!!

그래서 big에서 2를 빼서 small에 넣어준다

 

small 2 1

big 3

(답: 2)

 

 

이런식으로 계속 하면 된다.

참고로, 맨 처음에 큐가 비어있을 때는 굳이 경우를 나눠야하는게 귀찮아서

small에 -99999, big에 99999로 초기값을 하나씩 넣어주면 그냥 된다.

 

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int N; cin >> N;
    priority_queue<int> small;
    priority_queue<int, vector<int>, greater<int>> big;
    small.push(-99999);
    big.push(99999);
    while (N--) {
        int tmp; cin >> tmp;
        if (tmp <= big.top()) {
            small.push(tmp);
            if (small.size() - big.size() >= 2) {
                int a = small.top();
                small.pop();
                big.push(a);
            }
        }
        else {
            big.push(tmp);
            if (big.size() > small.size()) {
                int a = big.top();
                big.pop();
                small.push(a);
            }
        }
        cout << small.top() << '\n';
    }
}