백준 2357 최솟값과 최댓값 Java [세그먼트 트리]

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

2357번: 최솟값과 최댓값

 

세그먼트 트리는 

• 특정 구간의 합(최솟값, 최댓값, 곱 등)을 구하는 데 사용하는 자료구조이다.
• 이진 트리의 형태이며, 특정 구간의 합을 가장 빠르게 구할 수 있다.
• 시간복잡도 O(logN)

최솟값, 최댓값을 구해야하므로 2개의 세그먼트 트리를 만들었다

예제 입력으로 최솟값 세그먼트 트리를 만들면

먼저 배열의 크기를 N * 4의 크기로 만든다 ( N보다 큰 2의 제곱수 X 2 개가 필요하므로 4를 곱해서 충분히 크게 만든다 )

0번 자리는 비우고 1 ~ 10 중의 최솟값을 1번 자리에 넣는데

1 ~ 5 까지 최솟값과 6 ~ 10까지 최솟값 중에서 작은 값을 넣는다

1 ~ 5와 6 ~ 10의 최솟값을 구하기 위해 재귀를 사용하여 각각 2, 3번 자리에 넣는다

1 ~ 5는 1 ~ 3과 4 ~ 5 중 작은 값을 넣는다

1 ~ 3과 4 ~ 5의 최솟값을 구하기 위해 재귀를 사용하여 2 x 2인 4번 자리와, 2 x 2 + 1인 5번 자리에 넣는다

1 ~ 3은 1 ~ 2과 3 ~ 3 중 작은 값을 넣는다

1 ~ 2과 3 ~ 3의 최솟값을 구하기 위해 재귀를 사용하여 4 x 2인 8번 자리와, 4 x 2 + 1인 9번 자리에 넣는다

3 ~ 3은 값이 같으므로 재귀를 안하고 3의 값을 넣고 리턴한다

1 ~ 3은 1 ~ 1과 2 ~ 2 중 작은 값을 넣는다

1 ~ 1과 2 ~ 2의 최솟값을 구하기 위해 8 x 2인 16번 자리와, 8 x 2 + 1인 17번 자리에 넣고 리턴한다

 

이 과정을 반복하여 트리 구조로 만든 후에

특정 구간을 입력해서 트리에서 최솟값 또는 최댓값을 찾는다

 

import java.io.*;
import java.util.*;

public class Main {
    static int[] minTree;
    static int[] maxTree;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        minTree = new int[N * 4];
        maxTree = new int[N * 4];
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) arr[i] = Integer.parseInt(br.readLine());
        makeTree(0, N - 1, 1, arr, true);
        makeTree(0, N - 1, 1, arr, false);

        for (int m = 0; m < M; m++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            sb
                .append(findMinimum(0, N - 1, 1, a - 1, b - 1))
                .append(" ")
                .append(findMaximum(0, N - 1, 1, a - 1, b - 1))
                .append("\n");
        }

        System.out.println(sb);
    }

    static int makeTree(int start, int end, int index, int[] arr, boolean isMin) {
        if (start == end) {
            if (isMin) minTree[index] = arr[start];
            else maxTree[index] = arr[start];
            return arr[start];
        }
        int mid = (start + end) / 2;
        if (isMin) minTree[index] = Math.min(makeTree(start, mid, index * 2, arr, isMin), makeTree(mid + 1, end, index * 2 + 1, arr, isMin));
        else maxTree[index] = Math.max(makeTree(start, mid, index * 2, arr, isMin), makeTree(mid + 1, end, index * 2 + 1, arr, isMin));
        return isMin ? minTree[index] : maxTree[index];
    }

    static int findMinimum(int start, int end, int index, int left, int right) {
        if (left > end || right < start) return 1000000001;
        if (left <= start && right >= end) return minTree[index];
        int mid = (start + end) / 2;
        return Math.min(findMinimum(start, mid, index * 2, left, right), findMinimum(mid + 1, end, index * 2 + 1, left, right));
    }

    static int findMaximum(int start, int end, int index, int left, int right) {
        if (left > end || right < start) return 0;
        if (left <= start && right >= end) return maxTree[index];
        int mid = (start + end) / 2;
        return Math.max(findMaximum(start, mid, index * 2, left, right), findMaximum(mid + 1, end, index * 2 + 1, left, right));
    }
}