<Algorithm> 61. 2357번 최대값과 최소값(Segment Tree)

2357번 최대값과 최소값

• 기본 세그먼트 트리 알고리즘 문제, 재귀를 활용하기는 방법을 배우기에 좋은 문제라 생각한다
• 처음에 Max Min을 한번에 2차원 배열로 처리하려고 했는데 Min을 할때 Max의 재귀가 다시 돌아간다는 것을 생각하지 못했다.
• Max와 Min을 분리해서 처리를 하였다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main {
 
    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()) + 1;
        int M = Integer.parseInt(st.nextToken());
        int[] arr = new int[N];
        ArrayList<int[]> ans = new ArrayList<>();
        
        int[]temp = new int[1 << 18];
        int[]temp2 = new int[1 << 18];
 
        
        
        for (int i = 1; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
 
        init(0,arr, temp, 1, 1, N - 1);
        init(1,arr, temp2, 1, 1, N - 1);
        
        for (int i = 0; i < M; i++) {
            int res[] = new int[2];
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            res[0] = search(0, temp, 1, 1, N - 1, a, b);
            res[1] = search(1, temp2, 1, 1, N - 1, a, b);
            ans.add(res);
 
        }
 
        for (int[] lo : ans) {
            System.out.println(lo[1] + " " + lo[0]);
        }
 
    }
 
    private static int init(int check,int arr[], int[] temp, int node, int start, int end) {
        // 세그먼트 트리 초기화
        if (start == end) {
            // 마지막 노드에 배열값 저장 즉 가장 밑단 노드들에게 arr[]의 순서대로 값이 저장된다. 
            temp[node] = arr[start]; 
            return temp[node];
 
        } else {
 
            int mid = (start + end) / 2;
 
            if(check == 0) {
                temp[node] = Math.max(init(check,arr, temp, node * 2, start, mid),
                        init(check,arr, temp, node * 2 + 1, mid + 1, end));
                return temp[node];                
                // 왼쪽 오른쪽 탐색, 원리는 왼쪽맨 밑단까지 호출한뒤 
                //arr[]값 저장 그다음에 오른쪽 탐색 arr[] 저장 비교 부모노드에 저장 -> 재귀
            }else {
                temp[node] = Math.min(init(check,arr, temp, node * 2, start, mid),
                        init(check,arr, temp, node * 2 + 1, mid + 1, end));
                return temp[node];
            }
 
        }
 
    }
 
    private static int search(int check,int[] temp, int node, int start, int end, int left, int right) {
        
        int res;
        if (left > end || right < start) {
            if(check == 0) {
                res = Integer.MIN_VALUE;                
            }else {                
                res = Integer.MAX_VALUE;
            }
            return res;
            // 범위를 완전히 벗어나는 경우 , 탐색할 필요가 없을때!!
        }
 
        else if (left <= start && right >= end) {
            return temp[node];
            // left right에 구간이 포함 될 경우 출력 , ex) 3~4 in 2~4, 3~5
            // left start end right
        } else {
            // start left right end 일경우 , left start right end 일경우  
            int mid = (start + end) / 2;
            if(check == 0) {
                res = Math.max(search(check, temp, node * 2, start, mid, left, right)
                        , search(check, temp, node * 2 + 1, mid + 1, end, left, right));                
            }else {
                res = Math.min(search(check, temp, node * 2, start, mid, left, right)
                        , search(check, temp, node * 2 + 1, mid + 1, end, left, right));
            }
            return res;
        }
 
    }
 
}