[JAVA] 백준 2357 최솟값과 최댓값

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

2357번: 최솟값과 최댓값

문제 분석

N개의 정수 범위에서 a ~ b까지의 최댓값과 최솟값을 구해라. a, b쌍이 최대 10만 개 주어질 수 있음!

=> 각 a, b의 쌍에 대해 최솟값과 최댓값을 구하면 시간초과 발생

해결 전략

구간 합을 로그의 시간복잡도롤 구할 수 있는 세그먼트 트리 (이진 트리의 형태로 왼쪽, 오른쪽 자식을 재귀적으로 탐색)

최댓값과 최솟값을 구하기 위한 세그먼트 트리를 만들자

- mode에 따라 최솟값, 최댓값 메서드 구현

- 리프 노드를 제외한 노드에는 최댓값과 최솟값의 정보를 가짐

- 기존의 sum 연산 대신 find 연산을 수행!

** root 노드는 1번 노드부터 init, find 메서드 시작, arr: 1번 부터 값 가지게 하기

코드

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

public class Main {
    public static void main(String[] args) throws Exception {
        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());
        int[] arr = new int[N+1];
        for(int i=1;i<=N;i++) arr[i] = Integer.parseInt(br.readLine());

        int[] maxTree = new int[4*N];
        int[] minTree = new int[4*N];
        init(arr, maxTree, 1, 1, N, 1);
        init(arr, minTree, 1, 1, N, 0);

        for(int i=0;i<M;i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            int min = find(minTree, 1, 1, N, a, b, 0);
            int max = find(maxTree, 1, 1, N, a, b, 1);
            sb.append(min+" "+max).append('\n');
        }

        System.out.println(sb);
    }

    public static int init(int[] arr, int[] tree, int node, int start, int end, int mode){
        if(start==end) return tree[node] = arr[start];

        int mid = (start+end)/2;
        int left = init(arr, tree, node*2, start, mid, mode);
        int right = init(arr, tree, node*2+1, mid+1, end, mode);

        if(mode==1) return tree[node] = Math.max(left, right);
        else return tree[node] = Math.min(left, right);
    }

    public static int find(int[] tree, int node, int start, int end, int left, int right, int mode){
        if(end < left || start > right){
            if(mode==0) return Integer.MAX_VALUE;
            else return 0;
        }
        if(left<=start && end<=right) return tree[node];

        int mid = (start+end)/2;
        int lc = find(tree, node*2, start, mid, left, right, mode);
        int rc = find(tree, node*2+1, mid+1, end, left, right, mode);

        if(mode==0) return Math.min(lc, rc);
        else return Math.max(lc, rc);
    }
}