[BOJ]10868. 최솟값

# 문제링크

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

# 알고리즘

- Segment Tree를 사용해서 풀어야 한다.

- https://palyoung.tistory.com/64

# 풀이

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class BOJ10868 {
    static int arr[];
    static int N, M;
    static int a, b;
    public static void main(String[] args) throws IOException {
        //System.setIn(new FileInputStream("src\\sample.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder("");
        
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new int[N];
        
        for (int i=0; i<N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        
        SegmentTree segObj = new SegmentTree(arr, N);
        //segObj.print();
        
        for (int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            sb.append(segObj.query(a-1, b-1, 1, 0, N-1) + "\n");
        }
        System.out.println(sb);
    }
}
 
class SegmentTree {
    long segmentArr[];
    
    SegmentTree(int arr[], int N){
        segmentArr = new long[N*4];
        Arrays.fill(segmentArr, Integer.MAX_VALUE);
        init(arr, 0, N-1, 1);
    }
    
    long init(int arr[], int left, int right, int node) {
        if (left == right) return segmentArr[node] = arr[left];
        int mid = (left+right)/2;
        return segmentArr[node] = Math.min(init(arr, left, mid, node*2), init(arr, mid+1, right, node*2+1));
    }
 
    long query(int sIdx, int eIdx, int node, int nodeLeft, int nodeRight) {
        if (sIdx > nodeRight || eIdx < nodeLeft) return Integer.MAX_VALUE;
        if (sIdx <= nodeLeft && eIdx >= nodeRight) return segmentArr[node];
        int mid = (nodeLeft + nodeRight)/2;
        return Math.min(query(sIdx, eIdx, node*2, nodeLeft, mid), query(sIdx, eIdx, node*2+1, mid+1, nodeRight)); 
    }
    
    void print() {
        for (int i=0; i<segmentArr.length; i++) {
            System.out.printf("%d, ", segmentArr[i]);
        }
        System.out.println();
    }
}

# 회고

- segment tree 생성시 segmentArr에 초기값을 MAX로 설정해야한다.

  - Arrays.fill(segmentArr, Integer.MAX_VALUE);

- 자식이 있는 "부모노드"는 자식 노드들의 최솟값을 가지고 있어야 한다.

  - segmentArr[node] = Math.min(init(arr, left, mid, node*2), init(arr, mid+1, right, node*2+1));