[boj] (g2) 1655 가운데를 말해요

강신현·2022년 5월 10일

boj

[코딩테스트] 컴공선배 - 알고리즘 캠프

목록 보기

134/141

✅ 우선순위큐

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

1. 해결 로직

N은 1보다 크거나 같고, 100,000보다 작거나 같기 때문에
수를 입력할 때마다 정렬하여 중간값을 구하면 시간초과가 날 것이다.
따라서 우선순위큐를 사용하여 입력할 때마다 자동으로 정렬되게 할 것인데 이때도 중간값을 구하기 위해서는 중간까지 값을 빼고 다시 넣어야 하기 때문에 시간초과가 날 것이다.

중간값을 구하는 것이 목표이므로 최대힙과 최소힙을 같이 사용하여 반씩 넣어주면된다.

최대힙과 최소힙의 원소 개수가 동일해야 하므로 사이즈가 같을 때는 일단 최대힙에 넣고, 사이즈가 다를 때는 최대힙에 하나가 더 들어간 경우이므로 최소힙에 넣어준다.

이후 최대힙과 최소힙의 top원소의 크기를 비교하여 서로 바꾸던가 괜찮으면 그냥 둔다.

그러면 중간값은 최대힙의 top원소이다.

주어진 수의 개수가 홀수일 때는 최대힙에 우선으로 넣으므로 최대힙에 하나 더 들어가 있으므로 중간값은 최대힙의 top원소이다.

주어진 수의 개수가 짝수일 때는 중간에 있는 두 수 중에서 작은 수가 중간값이라고 했으므로 중간값은 최대힙의 top원소이다.

2. 코드

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>

using namespace std;

priority_queue<int> que_max;
priority_queue<int, vector<int>, greater<int>> que_min;
int N;

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

    cin >> N;
    for(int i=0;i<N;i++){
        int num;
        cin >> num;

        if(que_max.size() == que_min.size()) que_max.push(num);
        else que_min.push(num);

        if(!que_max.empty() && !que_min.empty() && que_max.top() > que_min.top()){
            int tmp_max = que_max.top();
            int tmp_min = que_min.top();
            que_max.pop();
            que_min.pop();
            que_max.push(tmp_min);
            que_min.push(tmp_max);
        }

        cout << que_max.top() << "\n";
    }

    // while(!que_max.empty()){
    //     cout << que_max.top() << " ";
    //     que_max.pop();
    // }
    // cout << "\n";
    // while(!que_min.empty()){
    //     cout << que_min.top() << " ";
    //     que_min.pop();
    // }
    // cout << "\n";
}