[BOJ] 1655번 : 가운데를 말해요

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

1655번: 가운데를 말해요

 

수 하나를 집어넣고 median값을 물어보는 query가 있을 때, 100000번의 query를 어떻게 0.1s(1e7번 내외의 iteration) 안에 처리할 것인가 하는 문제이다.

 

query의 개수를 $N$이라고 하고$(N \leq 100000)$, 정수의 범위를 $M$이라고 하자. $(M \leq 20000)$

 

처음에 떠올릴 수 있는 방법은 linked list로 수를 집어넣으며 직접 확인하는 방법 $O(N^2)$과

 

vector에 수를 집어넣으면서 매번 정렬하고 확인해주는 방법 $O(N^2\log{N})$ 이 있지만, 당연하게도 둘 다 time complexity 제한을 벗어난다.

 

따라서 $O(NlogN)$ 정도에서 해결해야겠다는 생각을 가져야 하는데, 이때 눈여겨 볼 점은 정수의 범위 $M$이 매우 작다는 것이다.

 

정수의 범위가 작을 때는 segment tree를 활용하면 효과적이다.

 

segment tree로 푸는 방식은 다음과 같다.

 

수를 넣는 query를 $O(logN)$만에 해결하고, median값을 $O(logN)$만에 찾는 함수를 만들어 해결한다. 이때, $[-10000, 10000]$범위의 수를 tree에 넣기 위해서 10000을 더해서 $[0, 20000]$으로 바꾸어서 넣어주었다.

 

개념과 구현은 크게 어렵지 않으니 내 코드의 find 함수를 참조하면 된다.

 

#include <iostream>
#include <vector>
#include <math.h>
#include <algorithm>
#include <queue>
#include <cstring>

using namespace std;

const int num_range = 20050;

int tree[5*num_range];

void update(int start, int end, int node, int target) {
    if(target < start || end < target) return ;
    tree[node]++;
    if(start==end) return;

    int mid = (start+end)/2;
    update(start,mid,node*2,target);
    update(mid+1,end,node*2+1,target);
}

int find(int start, int end, int node, int target) {
    if(start==end) return start-10000;

    int mid = (start+end)/2;
    if(tree[node*2] >= target) return find(start,mid,node*2, target);
    else return find(mid+1, end, node*2+1, target-tree[node*2]);
}

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

    int n, temp;
    cin>>n;
    for(int i = 1; i <=n ; i++) {
        cin>>temp;
        temp+=10000;
        update(0,20000,1,temp);
        int mid = (i%2==1)? i/2+1 : i/2;
        cout<<find(0,20000,1,mid)<<'\n';
    }

    return 0;
}

 

다만, 문제를 풀고 나서 확인해 보니 더 일반적인 풀이법은 min/max heap을 쓰는 것이라고 한다.

 

priority_queue 를 쓰면 사실 그쪽이 훨씬 간단하니 구글링해서 참조해보면 좋겠다.

 

내 코드는 내 github repository에서도 확인할 수 있다.

 

https://github.com/Jordano-Jackson/PS/blob/main/BOJ/1655/1655.cpp

GitHub - Jordano-Jackson/PS: Problem solving

---

References

Footnotes