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

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

1655번: 가운데를 말해요

매번 입력마다 정렬해서 가운데 값을 출력하면 시간초과가 난다ㅜㅜ

0.1초안에 해결해야하는데, 최대 입력이 100,000이므로 O(N^2)으로는 해결할 수 없다는 뜻이다.

이 문제는 2개의 우선순위 큐를 활용하면 되는데, 활용조건은 다음과 같다.

​

1. 최소 힙의 값들은 모두 최대 힙보다 커야한다.

2. 최대 힙의 크기가 최소 힙의 크기보다 1보다 크거나 같도록 유지한다.

3. 최대 힙과 최소 힙의 top 값을 비교해서 최소 힙의 top보다 최대 힙의 top이 더 크다면 값을 교환해준다.

위 3가지 조건을 잘 지키면, 최대 힙의 top값이 중간값이 된다.

​

왜 저걸 지켜야하냐??

1번 조건​부터 살펴보자. 아래 그림을 보면 이해가 쉬울 것이다.

이런 느낌으로 문제를 풀 것이기 때문에, 당연히 최소 힙의 값들은 최대 힙의 값들보다 커야한다.

그렇지만 실제로 중간 값을 밖으로 따로 빼서 풀진 않을 것이다!

​

2번 조건을 살펴보자.

- 최대 힙과 최소 힙의 크기가 같은 경우 = "백준이가 외친 수의 개수가 짝수 개인 경우"

ex) 1 2 3 4 5 6

이 때 최대 힙은 {1,2,3}, 최소 힙은 {4,5,6}

​

- 최대 힙이 최소 힙보다 크기가 1 큰 경우 = "백준이가 외친 수의 개수가 홀수 개인 경우"'

ex) 1 2 3 4 5

이 때 최대 힙은 {1,2,3}, 최소 힙은 {4,5}

​

어느 상황에서든 최대 힙의 top을 출력하면 중간 값이 나오도록 해주는 조건들이 1,2번 조건인 것이다

​

3번 조건을 살펴보자

항상 숫자가 예쁘게 주어지는 것은 아니다.

만약 5 0이라는 숫자를 백준이가 외쳤다고 해보자.

그럼 이때의 최대 힙엔 {5}가 들어가있고, 최소 힙엔 {0}이 들어가 있을 것이다.

위 상황은 1,2번 규칙에 위반되는 상황이다!

​

이를 방지하기 위해 각 힙의 top을 비교해서 최대 힙의 top이 최소 힙의 top보다 크면 두 힙의 top을 바꿔주는 것이다.

-> 그렇게 되면 깔끔하게 정렬된다.

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

int N,num;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> N;

    priority_queue<int> max_pq; // 작은 수들을 넣는 큐
    priority_queue<int,vector<int>,greater<>>  min_pq; // 큰 수들을 넣는 큐
    // 최소 힙의 값들은 최대 힙의 값들보다 무조건 커야한다! == swap해주자!
    // 그리고 최대 힙의 크기는 최소 힙보다 1보다 크거나 같아야한다. == 최대 힙에 값을 먼저 넣어주자!
    while (N--) {
        cin >> num;
        if (max_pq.size() == min_pq.size()) { // 사이즈가 같으면
            max_pq.push(num); // 최대 힙에 넣는다 -> why? mid가 2개일 경우 더 작은 수를 출력해야하기 때문
        }
        else {
            min_pq.push(num);
        }
        if (!max_pq.empty()&&!min_pq.empty()&&max_pq.top()>min_pq.top()) {
            // 둘다 비어있지않고, 작은 값들 중 최대 값이 큰 값들 중 최소 값보다 크면
            // 두 힙의 top을 swap 해준다!
            int max_val, min_val;
            max_val = max_pq.top();
            min_val = min_pq.top();
            max_pq.pop();
            min_pq.pop();
            max_pq.push(min_val);
            min_pq.push(max_val);
        }
        cout << max_pq.top() << '\n';
    }
}