백준 9426번 중앙값 측정 (JAVA)

백준 9426번 중앙값 측정

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

9426번: 중앙값 측정

 

문제

기상학에서 주요 사용하는 대표값은 중앙값이다. (중앙값의 정의는 힌트에 나와있다)

상근이는 1초에 한 번씩 온도를 재는 기계를 가지고 있고, 이 기계에 들어갈 소프트웨어를 작성하려고 한다. 기계에는 작은 디지털 디스플레이가 하나 달려있다. 매 초마다 디스플레이는 지난 K초동안 측정한 온도의 중앙값을 화면에 보여준다.

상근이는 소프트웨어를 기계에 올리기 전에 컴퓨터에서 테스트해보려고 한다.

총 N초 동안 측정한 온도가 주어졌을 때, 디스플레이에 표시된 중앙값의 합을 구하는 프로그램을 작성하시오. 즉, N개의 수가 주어졌을 때, 길이가 K인 연속 부분 수열 N-K+1개의 중앙값의 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 250,000, 1 ≤ K ≤ 5,000, K ≤ N)

둘째 줄부터 N개 줄에 측정한 온도가 순서대로 주어진다. 온도는 0보다 크거나 같고, 65535보다 작거나 같은 정수이다.

출력

길이가 K인 모든 연속 부분 수열의 중앙값의 합을 출력한다.

---

소스 코드

- 인덱스트리/세그먼트 트리 기본 유형이라고 생각했는데 우선순위 큐로도 해결 가능함

- 인덱스트리로 풀었음

- 최소/최대 찾기, 구간합 구하기에 이어 많이 나오는 특정 값 찾기 유형

- K값의 크기만큼 범위가 하나씩 이동(슬라이딩 윈도우 개념)한다고 이해해야 함

  > 이 부분은 Deque 로 구현

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Deque;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
    private static int N, K;
    private static long Ans;
    private static final int MAX = 65535; // 온도의 최대값이 65535인 정수
    private static int[] indexTree;
    private static int leafCnt;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        Ans = 0;
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        leafCnt = 1;
        while (leafCnt < MAX) {
            leafCnt <<= 1;
        }

        indexTree = new int[leafCnt * 2];

        Deque<Integer> q = new LinkedList<>();

        for (int i = 1; i < N + 1; i++) {
            int now = Integer.parseInt(br.readLine());
            update(now, 1);
            q.offer(now);
            if (i >= K) {
                Ans += search((K + 1) / 2);
                int poll = q.poll();
                update(poll, -1);
            }
        }
        bw.write(String.valueOf(Ans) + "\n");
        bw.flush();
        bw.close();
        br.close();
    }

    private static void update(int idx, int diff) {
        idx += leafCnt;
        while (idx != 0) {
            indexTree[idx] += diff;
            idx >>= 1;
        }
    }

    private static int search(int k) {
        int idx = 1;
        while (idx < leafCnt) {
            idx <<= 1;
            if (indexTree[idx] < k) {
                k -= indexTree[idx];
                idx++;
            }
        }
        return idx - leafCnt;
    }
}