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

이 문제는 우선순위 큐를 이용해서 풀었다.

 

시간 제한이 0.1초이므로 C++ 기준 1,000만 번의 연산만을 사용해야한다.

또한 입력 정수 N의 최댓값이 100,000이므로 O(N log N) 알고리즘을 구현해야한다.

 

이 문제의 핵심은 우선순위 큐를 두개를 두는 것이다. 양쪽에 우선순위 큐가 있다고 생각하고, 왼쪽에는 최대 힙, 오른쪽에는 최소 힙을

놓고 중간값을 찾는 것이다.

 

두 큐가 모두 비어있지 않을 때가 중요한데, 일단 범위에 맞게 현재 숫자를 집어넣고, 큐의 크기 비교를 통해 문제를 해결했다.

숫자 개수의 합이 홀수일 때는 왼쪽 큐가 사이즈가 1 더 크게 만들고, 왼쪽 큐의 top을 출력하는 방식으로 구현했고,

짝수일 때는 왼쪽과 오른쪽의 사이즈가 같게 만들어 왼쪽 큐의 top을 출력하는 방식으로 구현했다.

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

#define MAX 100000

int N;
int input[MAX];

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

    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> input[i];
    }

    priority_queue<int, vector<int>, greater<int>> rightPQ;
    priority_queue<int, vector<int>, less<int>> leftPQ;

    for (int i = 0; i < N; i++) {
        int present = input[i];

        if (leftPQ.empty() && rightPQ.empty()) {
            leftPQ.push(present);
            cout << present << '\n';
        }
        else if (!leftPQ.empty() && rightPQ.empty()) {
            int leftNum = leftPQ.top();

            if (leftNum < present) {
                rightPQ.push(present);
                cout << leftNum << '\n';
            } else {
                leftPQ.pop();
                rightPQ.push(leftNum);
                
                leftPQ.push(present);
                cout << present << '\n';
            }
        }
        else if (!leftPQ.empty() && !rightPQ.empty()) {
            int leftNum = leftPQ.top();
            int rightNum = rightPQ.top();

            if (leftNum <= present && present <= rightNum) {
                leftPQ.push(present);
            } else if (present < leftNum) {
                leftPQ.push(present);
            } else if (present > rightNum) {
                rightPQ.push(present);
            }

            if ((leftPQ.size() + rightPQ.size()) % 2 == 1) {
                if (rightPQ.size() > leftPQ.size()) {
                    while (leftPQ.size() != rightPQ.size() + 1) {
                        int temp = rightPQ.top();
                        rightPQ.pop();
                        leftPQ.push(temp);
                    }
                } else if (rightPQ.size() + 1 < leftPQ.size()) {
                    while (leftPQ.size() != rightPQ.size() + 1) {
                        int temp = leftPQ.top();
                        leftPQ.pop();
                        rightPQ.push(temp);
                    }
                }
                cout << leftPQ.top() << '\n';
            } else {
                if (rightPQ.size() > leftPQ.size()) {
                    while (leftPQ.size() != rightPQ.size()) {
                        int temp = rightPQ.top();
                        rightPQ.pop();
                        leftPQ.push(temp);
                    }
                } else if (leftPQ.size() > rightPQ.size()) {
                    while (leftPQ.size() != rightPQ.size()) {
                        int temp = leftPQ.top();
                        leftPQ.pop();
                        rightPQ.push(temp);
                    }
                }
                cout << leftPQ.top() << '\n';
            }
        }
    }
    
    return 0;
}