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

문제

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

설명

• 시간복잡도를 구하는 부분에서 큰일날뻔했다.... 이유는 트리 맥스heap, minheap의 삽입 삭제는 O(logN)인데 NlogN으로 생각하고 있었다.....

• 아무것도 없는 상태에서 min, maxheap을 만들때 n개의 배열에 대해서 heapify 과정이 필요하기 때문에 nlogn이 필요하다

• 다시 문제로 돌아온다면 가위바위보였나? 앞에 푼문제랑 동일해서 지우고 풀기보다는 새로운데 똑같은 문제를 풀었다...

• 여기서 주의점 현재 사이즈가 동일할 경우에서 새로운 값이 maq.top()보다 큰 경우

  • 큰 경우 바로 mnq에 넣고 mnq의 재정렬을 이룬 다음 mxq에 mnq.top을 넣는다 왜냐? 사이즈가 동일하다면 이번에 들어오는 값이 중간값의 후보가 될 수 있기때문에 mnq에 넣고나서 재정렬된 값을 다시 mxq에 넣는 것이다.

else if (mxq.size() == mnq.size()) {    //  1 3 2
            if (n > mxq.top()) {  // 2가 들어왔네?
                mnq.push(n); // 2를 mnq에 넣자 ->  2 3으로 변신!
                mxq.push(mnq.top());  // 이동쪽 check !!  -> 2를 mxq에 넣자, 2 1로 변신
                mnq.pop();
                //최종 2 1 | 3이된다 
            }

시간복잡도

• 최대 n이 10만이다 -> 그런데 큐가 두개인데 하나의 큐에서 최대 longN이 발생한다 그럼 10만 * long10^5 = 50만정도로 예상!

소스

#include <bits/stdc++.h>

#define endl '\n'

using namespace std;

int n;
//현재까지 외친 수가 짝수이면 1   5 
int main() {

    ios_base::sync_with_stdio(0); cin.tie(0);
    //100000(10^5) * logn -> 10만 * log10만 -> 50만 
    int t = 0; cin >> t;
    priority_queue<int, vector<int>> mxq;
    priority_queue<int, vector<int>, greater<int>> mnq;
    for (int i = 0; i < t; i++)
    {
        cin >> n;
        if (mxq.empty()) mxq.push(n);             
        else if (mxq.size() == mnq.size()) {    //  1 3 2
            if (n > mxq.top()) {  // 2가 들어왔네?
                mnq.push(n); // 2를 mnq에 넣자 ->  2 3으로 변신!
                mxq.push(mnq.top());  // 이동쪽 check !!  -> 2를 mxq에 넣자, 2 1로 변신
                mnq.pop();
                //최종 2 1 | 3이된다 
            }
            else {
                mxq.push(n);
            }
        }
        else if (mxq.size() > mnq.size()) {
            if (n > mxq.top()) mnq.push(n);
            else {
                mnq.push(mxq.top());
                mxq.pop();
                mxq.push(n);
            }
        }
        cout << mxq.top() << endl;
    }
    return 0;
}