[baekjoon] 1655

가운데를 말해요

문제

백준이는 동생에게 "가운데를 말해요" 게임을 가르쳐주고 있다. 백준이가 정수를 하나씩 외칠 때마다 동생은 지금까지 백준이가 말한 수 중에서 중간값을 말해야 한다. 만약, 그동안 백준이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다.

예를 들어 백준이가 동생에게 1, 5, 2, 10, -99, 7, 5를 순서대로 외쳤다고 하면, 동생은 1, 1, 2, 2, 2, 2, 5를 차례대로 말해야 한다. 백준이가 외치는 수가 주어졌을 때, 동생이 말해야 하는 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그다음 N 줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -10,000보다 크거나 같고, 10,000보다 작거나 같다.

출력

한 줄에 하나씩 N 줄에 걸쳐 백준이의 동생이 말해야 하는 수를 순서대로 출력한다.

예제 입력

7
1
5
2
10
-99
7
5

예제 출력

1
1
2
2
2
2
5

풀이

새 입력이 들어올 때마다 정렬해서 중간값을 찾기에는 시간제한이 0.1초라 불가능하다.

중간값을 어떻게 찾을까 정렬된 수를 보다가 아이디어가 떠올랐다.

정렬된 수를 반으로 나눠 세워보면 이해가 쉽게 됐다.

왼쪽은 내림차순, 오른쪽은 오름차순으로 정렬된 걸 볼 수 있었다.

이 상태에서 출력해야하는 값은 왼쪽 블록의 2이다.

이걸로 하나의 규칙을 세워봤다.

 

1. 왼쪽 블럭(내림차순)의 가장 위에 것을 출력한다.

 

그럼 새로운 값이 추가됐을때는 어떻게 변화되어야 할지 끼워 맞춰 봤다.

각각 5, 2, -1이 추가됐을 때

각각 큰값, 중간값, 작은 값이 추가 됐을 때, 왼쪽 블록의 가장 위에 값이 중간값이 되도록 끼워 맞춘 결과이다.

2, 3번째 경우를 보면 두 블록의 개수가 같으면 왼쪽 블록에 값을 추가해 주는 걸 볼 수 있다.

 

2. 블럭의 개수가 같으면 새로운 값을 왼쪽 블록(내림차순)에 추가한다.

 

첫 번째 경우 2번 규칙을 따랐더니 원하는 블록의 모습이 아니었다.

5를 오른쪽 블록으로 옮기고 3을 왼쪽 블록으로 가져오기 위해 3번째 규칙을 세웠다.

 

3. 오른쪽 블록(오름차순)의 위 값이 왼쪽 블록(내림차순)의 위의 값보다 커야 한다, 그렇지 않으면 두 값을 바꿔준다.

 

3가지 규칙에 맞춰서 구현했다.

#include <iostream>
#include <queue>

using namespace std;

int main(){
    int n, number;
    cin.tie(NULL), cout.tie(NULL);
    cin >> n;

    priority_queue<int> descendingQueue;
    priority_queue<int, vector<int>, greater<int>> ascendingQueue;

    while(n != 0)
    {
        cin >> number;

        if(ascendingQueue.size() < descendingQueue.size() && descendingQueue.size() != 0)ascendingQueue.push(number);
        else descendingQueue.push(number);

        
        if(!ascendingQueue.empty() && !descendingQueue.empty()){
            if(ascendingQueue.top() < descendingQueue.top()){
                int a = ascendingQueue.top();
                int b = descendingQueue.top();

                ascendingQueue.pop();
                descendingQueue.pop();

                ascendingQueue.push(b);
                descendingQueue.push(a);
            }
        }
        cout << descendingQueue.top() << "\n";
        n--;
    }
}