🔗 Problem

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

👩‍💻 Code

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

// 최솟값과 최댓값

public class BJ2357 {

    static int n, m;
    static int[] arr;
    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());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        arr = new int[n+1];
        minTree = new int[4*n];
        maxTree = new int[4*n];

        for(int i = 1; i <= n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        initMinTree(1, n, 1);
        initMaxTree(1, n, 1);

        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            sb.append(findMin(1, n, 1, a, b) + " " + findMax(1, n, 1, a, b)).append("\n");
        }

        System.out.println(sb.toString());
    }

    private static int initMinTree(int start, int end, int idx) {

        if(start == end) {
            return minTree[idx] = arr[start];
        }

        int mid = (start + end) / 2;
        return minTree[idx] = Math.min(initMinTree(start, mid, idx*2), initMinTree(mid+1, end, idx*2+1));
    }

    private static int initMaxTree(int start, int end, int idx) {

        if(start == end) {
            return maxTree[idx] = arr[start];
        }

        int mid = (start + end) / 2;
        return maxTree[idx] = Math.max(initMaxTree(start, mid, idx*2), initMaxTree(mid+1, end, idx*2+1));
    }

    private static int findMin(int start, int end, int idx, int a, int b) {

        if(b < start || end < a) return Integer.MAX_VALUE;
        if(a <= start && end <= b) return minTree[idx];

        int mid = (start + end) / 2;
        return Math.min(findMin(start, mid, idx*2, a, b), findMin(mid+1, end, idx*2+1, a, b));
    }

    private static int findMax(int start, int end, int idx, int a, int b) {

        if(b < start || end < a) return Integer.MIN_VALUE;
        if(a <= start && end <= b) return maxTree[idx];

        int mid = (start + end) / 2;
        return Math.max(findMax(start, mid, idx*2, a, b), findMax(mid+1, end, idx*2+1, a, b));
    }
}

📌 Note

아이디어

• 새그먼트 트리 알고리즘 공부 후 풀었음
  
• 배열을 생성한 후 각 node가 트리 형태로 연결되어 있다고 가정
• 1~n까지의 nodes는 1 ~ n/2, n/2+1 ~ n 로 나누어 재귀로 값을 할당해줌
• parent node idx: x
• right leaf node idx: 2*x
• left leaft node idx: 2*x + 1

References

• https://cano721.tistory.com/38