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

문제 링크 : 1655번: 가운데를 말해요 (acmicpc.net)

1655번: 가운데를 말해요

> 풀이

 

입력을 한 번 받을 때마다 정렬을 하여 중간값을 찾아야 한다.

보통의 정렬을 쓰게되면 복잡도가 n x nlogn이 되는데 무조건 시간초과가 날 것 같다.

따라서 삽입 복잡도가 logn인 우선순위 큐를 쓰자

 

우선순위 큐를 하나만 쓸 경우 중간값을 찾기 힘들다. 따라서 최대힙, 최소힙 하나씩 두 개의 우선순위 큐를 써서 중간값을 찾도록 하자

 

최대힙  |   최소힙 순으로 두고 두 우선순위 큐의 개수를 같게 유지하면 중간값을 쉽게 찾을 수 있다

 

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

priority_queue<int, vector<int>, less<int> > pq1;
priority_queue<int, vector<int>, greater<int> > pq2;
int N, n;

int main(void) 
{
        scanf("%d", &N);
        for (int i = 0; i < N; i++) {
                scanf("%d", &n);
                if (i == 0) {
                        pq1.push(n);
                        printf("%d\n", n);
                        continue;
                }
                else if (pq2.size() == 0) {
                        if (pq1.top() <= n) pq2.push(n);
                        else {
                                int tmp = pq1.top();
                                pq1.pop();
                                pq1.push(n);
                                pq2.push(tmp);
                        }
                        printf("%d\n", pq1.top());
                        continue;
                }

                int m1 = pq1.top(), m2 = pq2.top();
                int s1 = pq1.size(), s2 = pq2.size();

                if (n >= m1 && n <= m2) {
                        if (s1 == s2) {
                                pq1.push(n);
                        }
                        else if (s1 > s2) {
                                pq2.push(n);
                        }
                }
                else if (n < m1) {
                        if (s1 == s2) {
                                pq1.push(n);
                        }
                        else if (s1 > s2) {
                                int tmp = pq1.top();
                                pq1.pop();
                                pq1.push(n);
                                pq2.push(tmp);
                        }
                }
                else {// n > m2
                        if (s1 == s2) {
                                int tmp = pq2.top();
                                pq2.pop();
                                pq2.push(n);
                                pq1.push(tmp);
                        }
                        else if (s1 > s2) {
                                pq2.push(n);
                        }
                }
                printf("%d\n", pq1.top());
        }
        return 0;
}