[BOJ / 인덱스 트리] 1572 중앙값

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

1572번: 중앙값

 

1572 중앙값

알고리즘 : 인덱스트리 / 이분탐색

알고리즘 중에 힙 두개를 사용하여 데이터가 순서대로 들어올 때마다 현재 쿼리에서 중앙값을 구하는 중앙값 알고리즘이 있습니다.

이 알고리즘은 지금까지 받은 전체 범위에서 중앙값을 구하는 반면, 해당 문제는 범위를 주어주고 그 내에서 중앙값을 구해야 하므로 위 알고리즘을 활용해서 풀이할 수 없습니다. ( O(NM)만 해도 TLE )

 

그렇기에 인덱스 트리의 맨 윗 인자를 현재까지 나온 수의 개수를 저장하는 방식을 이용합니다. 그리고 지금까지 저장된 수를 큐에 저장하고 K개가 넘어간다면 처리를 해주고 큐에서 처음 들어온 수를 POP하여 K개를 유지해줍니다. 인덱스 트리에서는 0을 카운트 할 수 없으므로 전체에 1을 더해주고 이분탐색으로 (1 ~ MAX + 1) 까지의 범위에서 골라 해당 번째의 인덱스 트리의 count 값이

중앙값 번째인 (K + 1)/2개인지 확인하면서 진행합니다. 그 전에 left와 right가 같아진다면 예외처리를 해주면 문제를 풀이할 수 있습니다.

 

 

 

< CODE >

#include <iostream>
#include <queue>

using namespace std;

#define MAX 65537

typedef long long int ll;

int n, k;
ll v[250005];
int tree[MAX + 2];

queue<int> q;

ll result = 0;

void update(int i, int diff)
{
    while (i < MAX)
    {
        tree[i] += diff;
        i += (i & -i);
    }
}

int find(int i)
{
    int ret = 0;

    while (i > 0)
    {
        ret += tree[i];
        i -= i & -i;
    }
    return ret;
}

ll bi()
{
    int l = 1;
    int r = 65537;
    int wanted = (k + 1) / 2;

    while (true)
    {
        int mid = (l + r) / 2;
        int cnt = find(mid);
        
        if (l == mid)
        {
            if (cnt < wanted)
                return r - 1;
            return l - 1;
        }

        if (cnt < wanted)
            l = mid;
        else
            r = mid;
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> k;

    for (int i = 1; i <= n; i++)
    {
        cin >> v[i]; 

        v[i] += 1;

        update(v[i], 1);
        q.push(v[i]);

        if (i >= k)
        {
            result += bi();
            update(q.front(), -1); q.pop();
        }
    }

    cout << result << '\n';

    return 0;
}

시간 : 88ms

 

태그 : #BOJ 중앙값 #백준 중앙값 #1572 중앙값 #중앙값 풀이 #중앙값 인덱스트리