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

문제는 다음과 같습니다.

사실 처음에는 시간을 간과해서 매번 정렬시키는 방법으로 했다가 ,, 시간초과가 났습니다 ^^..

이후에는 "우선순위 큐"라는 힌트를 얻고 다시 풀게 되었습니다.

저는 두 개의 우선순위 큐를 이용하여 문제를 풀었습니다.
상대적으로 작은 수들을 담는, "내림차순" 우선순위 큐와,
상대적으로 큰 수들을 담는, "오름차순" 우선순위 큐 입니다.

정렬이 아닌, 맨 앞 원소에서 답을 뽑아낼 것이기 때문에
작은 수들을 담는 우선순위 큐는 -> 내림차순 이어야 하고,
큰 수들을 담는 우선순위 큐는 -> 오름차순 이어야 합니다.

그러므로, 문제의 결과 출력은 항상 두 우선순위 큐 중 맨 앞에있는 -> top() 원소가 됩니다.

먼저, 제 전체 코드는 다음과 같습니다.

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


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

    priority_queue<int, vector<int>, less<int>> pq1;
    priority_queue<int, vector<int>, greater<int>> pq2;
    int n, t1, t2, tmp;
    cin>>n;
    cin>>t1>>t2;
    cout<<t1<<"\n";
    cout<<min(t1, t2)<<"\n";

    pq1.push(min(t1, t2)); pq2.push(max(t1, t2));

    for(int i=3; i<=n; i++){
        cin>>tmp;
        if(tmp < pq2.top()) pq1.push(tmp);
        else pq2.push(tmp);

        // 맞춰주는 과정 -> 차이가 최대 1 이하가 될 때까지
        while(pq1.size()-1 > pq2.size()){
            pq2.push(pq1.top());
            pq1.pop();
        }
        while(pq2.size()-1 > pq1.size()){
            pq1.push(pq2.top());
            pq2.pop();
        }

        // 출력과정
        if(pq1.size()>=pq2.size()) cout<<pq1.top()<<"\n";
        else cout<<pq2.top()<<"\n";
    }

    return 0;
}

과정은 다음과 같습니다.

1. 처음, 두번째 원소의 예외처리 해주기

cin>>t1>>t2;
cout<<t1<<"\n";
cout<<min(t1, t2)<<"\n";

pq1.push(min(t1, t2)); pq2.push(max(t1, t2));

입력받은 두 원소 중 더 작은 값을 pq1 큐로, 더 큰 값을 pq2 큐에 넣어줍니다.

이후 반복적으로 입력받는 원소에 대해서는 다음과 같습니다.

2. 먼저, 두 큐의 원소 개수의 차가 1 이하가 되도록 만들어주기

입력받은 원소에 대해서 pq1의 큐에 넣어줄지, pq2 큐에 넣어줄지 결정하고 큐에 원소를 삽입합니다.

cin>>tmp;
if(tmp < pq2.top()) pq1.push(tmp);
else pq2.push(tmp);

이후에, 중간값을 출력하기 전에
두 큐의 사이즈값이 1 이하가 되도록 만들어줍니다.
✅pq1의 top 또는 pq2의 top에서 답을 바로 꺼내기 위한 과정입니다

// 맞춰주는 과정 -> 차이가 최대 1 이하가 될 때까지
while(pq1.size()-1 > pq2.size()){
    pq2.push(pq1.top());
    pq1.pop();
}
while(pq2.size()-1 > pq1.size()){
    pq1.push(pq2.top());
    pq2.pop();
}

(조건을 만족하면 계속해서 while문을 수행합니다)

3. 답 출력하기

위 2번 과정을 통해, 두 큐를 원소의 차가 1 이하가 되도록 만들었습니다.

총 경우의 수는 3가지입니다.

case1: pq1.size() == pq2.size()
-> 입력받은 수가 짝수개인 경우입니다. 이 경우에는 더 작은 값을 출력해야 하므로, pq1.top()의 원소를 출력합니다.

case2: pq1.size () > pq2.size()
-> pq1.top()의 원소를 출력합니다.

case3: pq1.size() < pq2.size()
-> pq2.top()의 원소를 출력합니다.

이에 해당하는 코드는 다음과 같습니다.

// 출력과정
if(pq1.size()>=pq2.size()) cout<<pq1.top()<<"\n";
else cout<<pq2.top()<<"\n";

---