[BOJ 1655 // C++] 가운데를 말해요

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 1655번 문제인 가운데를 말해요이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/1655

1655번: 가운데를 말해요

이 문제에서는 매번 목록에 새로운 수가 하나씩 추가될 때, 그 목록의 크기순으로 중간번째인 수를 출력해야 한다. 만약 숫자가 짝수라면, 가운데에서 작은 수를 골라 출력해야 한다. 예를 들면 8개의 수 가운데 4번째로 작은 수를 출력해야 한다.

 

이 문제를 풀기 위해서는 다른 위치에 상관 없이 크기순으로 중간에 있는 값에만 빠르게 접근하면 되므로, 목록을 출력해야하는 중간번째를 기준으로 나눠서 중간번째보다 큰 수를 보관하는 우선순위 큐(priority queue)와 작은 수를 보관하는 우선순위 큐를 만드는 전략이 유효하다.

mid 변수에 기존 중간 위치의 값을 저장하자. 새로운 수를 입력받았을 때 이 값이 이전 출력값보다 크거나 같다면 큰 수를 보관하는 우선순위 큐에, 작다면 작은 수를 보관하는 우선순위 큐에 삽입한다. 그리고 두 우선순위 큐의 크기를 비교하면 현재 mid에 보관하고있는 값이 지금도 중간 위치에 있는 수인지 아닌지 알 수 있다.

mid에 보관된 값이 중간위치가 아니게 되었다면, mid를 적절한 우선순위 큐에 다시 넣고, 반대쪽 우선순위 큐에서 mid값을 새로 읽어온다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <queue>
using std::cin;
using std::cout;
using std::priority_queue;

priority_queue<int> smallvalues;
int mid;
priority_queue<int> largevalues;

int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0);
    
    int N; cin >> N;
    cin >> mid; cout << mid << '\n';
    for (int i = 1;i < N;i++) {
        int current; cin >> current;
        if (current >= mid) largevalues.push(-current);
        else smallvalues.push(current);
        if (largevalues.size() - smallvalues.size() == 2) {
            smallvalues.push(mid);
            mid = -largevalues.top(); largevalues.pop();
        }
        else if (largevalues.size() - smallvalues.size() == -1) {
            largevalues.push(-mid);
            mid = smallvalues.top(); smallvalues.pop();
        }
        cout << mid << '\n';
    }
    return 0;
}