[BOJ] 9426 중앙값 측정

1. 문제요약

9426번: 중앙값 측정 (acmicpc.net)

9426번: 중앙값 측정

1차원 배열이 주어지고 길이가 K 인 연속 부분 수열에 대해, N-K+1 개의 중앙값의 합을 구하는 프로그램을 작성하시오.

수 K 개의 중앙값은 ((K+1)/2) 번째로 작은 숫자이다. 인덱싱은 1번 부터 시작하며, K가 홀수인 경우를 처리하기 위해 1을 더한다.

 

2. 문제예제

 

 

3. 팩트추출

Fact 1 : 길이가 K 인 모든 연속 부분 수열을 구해야 되므로 슬라이딩 윈도우를 생각할 수 있다.

양 옆에 있는 숫자들만 연산에 추가하고 중간 부분에 있는 값을 재사용할 수 있다면 슬라이딩 윈도우가 적합할 수 있다.

하지만, 이 문제같은 경우 숫자를 양 옆에서 가져와도 어느 것이 중앙 값인지 슬라이딩 윈도우로 K 배열을 가져올 때마다 K 길이만큼 탐색해야 구할 수 있다. 다시 말해 배열 중앙에 있는 값들을 재활용할 수 없다.
 

Fact 2 : 각 구간을 효율적으로 탐색할 수 있는 자료구조를 사용한다면 빠르게 계산할 수 있다. 세그먼트 트리가 대표적인 방식이다. 세그먼트 트리는 자신을 포함한 모든 구역에 대해 값을 업데이트한다는 특징과 부모 노드로 올라갈수록 구간의정보가 합쳐진다는 특징이 있다. 해당 문제에서는 중앙값을 찾고 싶어하므로 자식 노드를 몇 개 가지고 있는지 카운트 정보를 가지고 있다면 쉽게 계산할 수 있다.

 

지문에서 소개한 중앙값을 M = (K+1)/2 이라고 할 때, 아래와 같은 방법으로 탐색할 수 있다.

tree[node*2] >= M : 왼쪽 자식 트리가 M 보다 크므로 자신보다 작은 값이 나올 때까지 왼쪽 트리를 재귀탐색한다.

tree[node*2] < M : 왼쪽 자식 트리가 M 보다 작으므로 M 에서 왼쪽 형제 노드 갯수만큼 빼주고 (M-tree[node*2]) 오른쪽 트리를 재귀탐색한다.

 

Fact 3 : 트리에 주어진 배열을 모두 삽입할 필요는 없다. 슬라이딩 윈도우 방식처럼 트리에 하나씩 넣고 빼어 쿼리 결과 값을 가져온다.

 

4. 문제풀이(수동)

(출처 : [BOJ] 백준 9426번 중앙값 측정 (Java) (tistory.com))

 

K 배열 내부 값들인 3, 4, 5 값을 세그먼트 트리에 삽입하면 3 4 5 인덱스를 포함한 부모노드들은 각 아래 자식노드들이 몇 개 있는지 카운트 정보를 가지고 있게 된다. 이를 통해 어디로 탐색하는지 알 수 있게 된다.

먼저 중앙값을 계산하면, (k+1/2) 공식에 따라 k=2 가 된다. 왼쪽 자식은 1개 밖에 없으므로 오른쪽 자식 트리에 있다는 것을 알 수 있으며, 오른쪽 트리를 순회하면서 왼쪽 자식의 갯수만큼 빼주어 탐색을 하는 것을 볼 수 있다.

 

5. 문제전략

문제 전략은 팩트 추출을 통해 알아보았다. 슬라이딩 윈도우 기법으로 K 개 만큼 세그먼트 트리에 삽입하고 쿼리를 각각 수행한다.

 

6. 소스코드

( [BOJ] 백준 9426번 중앙값 측정 (Java) (tistory.com) 소스코드를 공부하고, 주석을 달았습니다. )

public class Main {
    static final int SIZE = 65536;
    static int[] arr, tree;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        arr = new int[n+1];
        for(int i=1; i<=n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        tree = new int[SIZE*4];
        // 1 번부터 k 직전까지 노드 삽입
        for(int i=1; i<k; i++) {
            update(0,SIZE,1,arr[i],1);
        }
        int prev = 1;
        int mid = (k+1)/2;
        long ans = 0;
        // k 부터 n 까지 노드 삽입하면서 중앙값을 계산하고, 슬라이딩 윈도우 기법으로 K 배열을 움직인다.
        for(int i=k; i<=n; i++) {
            update(0,SIZE,1,arr[i],1);
            ans += find(0,SIZE,1,mid);
            update(0,SIZE,1,arr[prev++],-1);
        }
        System.out.println(ans);
    }

    static int update(int start, int end, int node, int index, int diff) {
        // 기저사례 1 : 타겟 인덱스가 범위 밖인 경우, skip
        if(index < start || end < index) {
            return tree[node];
        }
        // 기저사례 2 : 타겟 인덱스 안에 있으면서 start == end 값이 같다면 index 지점에 도착했다는 뜻
        if(start == end) {
            return tree[node] += diff;
        }

        int mid = (start + end) / 2;
        // 좌측 의 카운트와 우측의 카운트를 합친 값이 부모 카운트
        return tree[node] = update(start, mid, node*2, index, diff)+update(mid+1, end, node*2+1, index, diff);
    }

    static int find(int start, int end, int node, int k) {
        if(start == end) {
            return start;
        }

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