백준 1655 가운데를 말해요

문제

문제 분석

꽤나 재미있었던 문제였다.

우선 조건부터가 0.1초로 재미있었는데 10^7이라는 제약조건이 꽤나 문제의 접근방식을 제한했던 것 같다.

입력의 범위는 입력횟수 N에 대하여 1 <= N<=10^5 / 각 수 x에 대하여 범위는 -10^4<= x<= 10^4

가장 처음에 생각했던 것은 가장 쉽게 sort하고 중간 인덱스의 원소를 출력하는 것이었는데, 문제는 이 문제가 각 입력시마다 출력을 해야했기 때문에 sort에 걸리는 Nlog(N)를 N번(러프하게 보자면)시행해야 하므로 절대 안되는 방식이었다.

그리고 하나의 자료구조를 만드는 것에 대해서 고민해봤는데 완전 이진트리를 만들되, 하나의 노드에 대해서 왼쪽 자식은 부모노드보다 작고, 오른쪽 자식은 부모노드보다 큰 그런 트리를 정의하려 하였으나 문제는 리프가 다 차지 않을 때 중간값의 인덱스가 root이라는 보장이 없었다.

그런데 이 아이디어를 확장해보았다. 트리와 같이 하나의 노드와 두가지 서브트리로 나뉘는 방식에서 대신 하나의 노드와 두가지의 힙이 하나의 구조를 만드는 방식으로 말이다.  왼쪽 힙 / 중앙 / 오른쪽 힙 으로 나누고, 왼쪽과 오른쪽을 우선순위큐로 구현하여 노드가 하나 들어 올 때마다 왼쪽과 오른쪽 pq의 갯수를 체크하고 중앙을 연산하는 방식에 대해서  생각해보았다.

 

우선 하나의 노드가 추가되었을 때 현재 중앙값보다 작거나 같다면 왼쪽힙에 저장하고 크다면 오른쪽힙에 저장한다.

k개에 대해서 이미 작동이 잘 되었다고 가정한다면 그 구조는 반드시 다음과 같을것이다.

k-1/2, 1, k-1/2

만약 k-1이 홀수라면? -> 반드시 오른쪽 힙이 하나 더 많아야한다. 왜냐하면 왼쪽 힙이 하나 더 많다면 중앙값은 현재 1개로 나뉘어진 중앙 추측값이 아닌 왼쪽 힙에서 가장 큰 값이 될것이기 때문이다.

그래서 small_pq.size() <= large_pq.size()이 확실할것이다.

그렇다면 만약에 small_pq.size() + 2 == large_pq.size()가 된다면? 그렇다면 이전의 중앙값이 왼쪽 힙으로 들어가고, 오른쪽 힙에서 가장 작은값을 꺼내서 중앙값으로 만들어주면 왼쪽힙과 오른쪽힙의 크기는 같고, 중앙값이 도출되게 될것이다.

 

다음은 예시이다.

small.size /  mid/size  / large.size = 3 1 4 이러한 예시가 존재한다면 다음 노드가 추가된다면

1. 3 1 5

   -> 현재 mid값을 왼쪽 힙에 추가한 후 large에서 하나 빼서 mid로 만든다

2. 4 1 4

   -> 이전의 중앙값이 현재 중앙값일 것이다.

 

만약 왼쪽 힙의 갯수가 더 많아진다면 그런 경우는 존재할 수 없으므로 1번 경우의 수와 같이 하나를 빼서 mid로 만들어줘야한다.

왼쪽힙.size() <= 오른쪽힙.size()

왼쪽힙.size() + 2 >= 오른쪽힙.size()

이 두가지 경우의 수에 대해서 조금 더 생각해보면 쉬울 것 같다

코드

#include<stdlib.h>
#include<iostream>
#include<string.h>
#include<string>
#include<list>
#include<vector>
#include<stack>
#include<queue> // priority_queue 포함
#include<set>
#include<unordered_set>
#include<map>
#include<unordered_map>

#include<algorithm>
#include<math.h>
#include<climits> // 자료형 limit포함

using namespace std;

typedef long long int lld;
typedef unsigned long long int uld;
typedef unsigned int ui;

const int MY_INT_MAX = 2000000000;
// N <= 100,000
void solution()
{
    // code
    int n, mid;
    cin >> n;
    priority_queue<int,vector<int>, less<int>> small_pq;
    priority_queue<int,vector<int>, greater<int>> large_pq;
    cin >> mid;
    cout << mid << "\n";

    for(int i=1; i<n; i++)
    {
        int input_d;
        cin >> input_d;
        if(mid < input_d)
            large_pq.push(input_d);
        else
            small_pq.push(input_d);
        if(small_pq.size() != large_pq.size())
        {
            //s
            if(small_pq.size() > large_pq.size())
            {
                large_pq.push(mid);
                mid = small_pq.top();
                small_pq.pop();
            }
            if(small_pq.size() + 1 < large_pq.size())
            {
                small_pq.push(mid);
                mid = large_pq.top();
                large_pq.pop();
            }
        }
        cout << mid << "\n";
    }

}

int main ()
{
    iostream::sync_with_stdio(0); // 이제 C stdio의 입출력 사용 불가
    cin.tie(NULL);
    cout.tie(NULL); // 개행도 \n로 하도록 하자.
    solution();
    return 0;
}

개선점?

풀기 어려운 하나의 문제를 쉬운 문제들로 소분하는 연습을 조금 더 해보자