[백준] 2357번 최솟값과 최댓값 _ JAVA ( 주석 설명 )

풀이

구간 합 구하기에서 풀었던 방법은 '부모노드 = 왼쪽 자식노드 + 오른쪽 자식노드' 였다.

이 문제에서는

최솟값을 구할 때는 '부모노드 = Math.min(왼쪽 자식노드, 오른쪽 자식노드)'

최댓값을 구할 때는 '부모노드 = Math.max(왼쪽 자식노드, 오른쪽 자식노드)' 로 구하면 된다.

+

min∙max 세그먼트 트리를 초기화할 때(init 함수)

구간에서의 min∙max를 구할 때(query 함수)

전체 탐색 범위를 1~N, 0~N-1 / 구간 탐색 범위 left right를 left-1~right-1, left~right 로 설정하면 된다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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());
        //최소∙최댓값 찾으려는 범위 개수
        int M = Integer.parseInt(st.nextToken());
        int[] ary = new int[N+1];


        int h = (int) Math.ceil(Math.log(N)/Math.log(2)); //트리의 높이
        int tree_size = 1 << (h+1); //트리 크기
        int[] min_tree;
        int[] max_tree;

        for(int i=0;i<N;++i){
            ary[i] = Integer.parseInt(br.readLine());
        }

        //세그먼트 트리
        //부모가 자식 노드 중 최소∙최댓값을 선택해서 갖게끔 초기화
        min_tree = new int[tree_size];
        init(ary, min_tree, 1, 0, N-1, true);
        max_tree = new int[tree_size];
        init(ary, max_tree, 1, 0, N-1, false);

        StringBuilder sb = new StringBuilder();
        //a~b번째 범위 중 최소∙최댓값 찾기
        for(int i=0;i<M;++i){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            //a~b 구간 최소∙최댓값 찾기
            //min을 구할 때는 min_tree, isMin(true)를 넣어서 최솟값 구하기
            //max을 구할 때는 max_tree, isMin(false)를 넣어서 최대값 구하기
            int min = query(min_tree, 1, 0, N-1, a-1, b-1, true);
            int max = query(max_tree, 1, 0, N-1, a-1, b-1, false);

            sb.append(min).append(' ').append(max).append('\n');
        }

        System.out.println(sb);
    }

    public static int init(int[] ary, int[] tree, int node, int start, int end, boolean isMin){
        //리프노드일 경우
        //입력 배열 값 tree 노드에 넣어주기
        if(start==end)
            return tree[node] = ary[start];

        int mid = (start+end)/2;

        //isMin에 따라 min_tree-최소값 트리 or max_tree-최대값 트리 만들기
        if(isMin)
            return tree[node] = Math.min(init(ary, tree, node*2, start, mid, true), init(ary, tree, node*2+1, mid+1, end, true));
        else
            return tree[node] = Math.max(init(ary, tree, node*2, start, mid, false), init(ary, tree, node*2+1, mid+1, end, false));
    }

    //left~right 구간에서 min / max 알아내기
    public static int query(int[] tree, int node, int start, int end, int left, int right, boolean isMin){
        //범위를 벗어난 경우
        if(right<start || left>end){
            if(isMin)
                return Integer.MAX_VALUE;
            else
                return Integer.MIN_VALUE;

        }

        //범위 내에 있는 경우
        if(left<=start && right>=end){
            return tree[node];
        }

        int mid = (start+end)/2;

        int lval, rval;

        //구간 내에서 최솟값을 찾는 경우
        if(isMin) {
            lval = query(tree, node*2, start, mid, left, right, true);
            rval = query(tree, node*2+1 , mid + 1, end, left, right, true);
            return Math.min(lval, rval);
        }

        //구간 내에서 최댓값을 찾는 경우
        else {
            lval = query(tree, node*2, start, mid, left, right, false);
            rval = query(tree, node*2+1, mid + 1, end, left, right, false);
            return Math.max(lval, rval);
        }
    }
}