[BOJ] 1306 달려라 홍준 (JAVA)

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

1306번: 달려라 홍준

세그먼트 트리와 슬라이딩 윈도우를 이용하여 풀 수 있는 문제입니다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer st;
    static int N, M;
    static int[] input, result;

    public static void main(String[] args) throws Exception {

        st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        input = new int[N + 1];
        result = new int[N * 4];
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 1; i <= N; i++) {
            input[i] = Integer.parseInt(st.nextToken());
        } // end of input

        make(1, N, 1);

        int head = M * 2 - 1;
        int tail = 1;

        while(head <= N) {
            sb.append(select(1, N, 1, tail++, head++)).append(" ");
        }

        System.out.print(sb.toString());

    }

    static int select(int startIndex, int endIndex, int treeIndex, int startRange, int endRange) {

        if(endIndex < startRange || endRange < startIndex) return 0;

        if(startRange <= startIndex && endIndex <= endRange) return result[treeIndex];

        int midIndex = (startIndex + endIndex) / 2;
        int left  = select(startIndex, midIndex, treeIndex * 2, startRange, endRange);
        int right = select(midIndex + 1, endIndex, treeIndex * 2 + 1, startRange, endRange);

        return Math.max(left, right);

    }

    static int make(int startIndex, int endIndex, int treeIndex) {

        if(startIndex == endIndex) return result[treeIndex] = input[startIndex];

        int midIndex = (startIndex + endIndex) / 2;
        int left  = make(startIndex, midIndex, treeIndex * 2);
        int right = make(midIndex + 1, endIndex, treeIndex * 2 + 1);

        return result[treeIndex] = Math.max(left, right);

    }
	
}