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

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

2357번: 최솟값과 최댓값

 

세그먼트 트리를 활용해서 풀 수 있는 문제다. 

https://chamggae.tistory.com/113 세그먼트 트리

 

 

기존 트리의 루트에 각 자식 노드의 합을 저장하는 방식에서 각 자식 노드의 최소/최대값 을 저장해주었다.

 

다른 세그먼트 트리 문제와 다르게 업데이트 함수를 구현할 필요가 없어서 편했다. 

 

import java.util.Scanner;

public class Main {

    private static Tree[] Trees;
    private static int[] Number;
    private static int N;
    private static int M;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        N = scanner.nextInt();
        M = scanner.nextInt();

        int h = (int) Math.ceil(Math.log(N)/Math.log(2));
        int treeSize = (int) Math.pow(2, h+1);

        Trees = new Tree[treeSize];
        Number = new int[N+1];

        for(int i = 1; i<=N; i++) {
            Number[i] = scanner.nextInt();
        }

        for(int i = 0; i<treeSize; i++) {
            Trees[i] = new Tree();
        }
        makeTree(1, N, 1);
        for(int i = 0; i<M; i++) {
            int left = scanner.nextInt();
            int right = scanner.nextInt();

            Tree result = getMinMaxNode(1, N, left, right, 1);

            System.out.println(result.min+" "+result.max);
        }

    }

	/*
    	트리 구현 
    */
    public static Tree makeTree(int start, int end, int index) {
        if(start == end) {
            Trees[index].min = Number[start];
            Trees[index].max = Number[start];

            return Trees[index];
        }

        int mid = (start+end) / 2;
        Tree l_child = makeTree(start, mid, index*2);
        Tree r_child = makeTree(mid+1,  end, index*2+1);

        Trees[index].min = Math.min(l_child.min, r_child.min);
        Trees[index].max = Math.max(l_child.max, r_child.max);
        return Trees[index];
    }

	/*
    	최소, 최대 구하기
    */
    public static Tree getMinMaxNode(int start, int end, int left, int right, int index) {
        if (start > right || end < left ) {
            return new Tree();
        }

        if (start >= left && end <= right) {
            return Trees[index];
        }
        int mid = (start+end) / 2;
        Tree l_child = getMinMaxNode(start, mid, left, right, index*2);
        Tree r_child = getMinMaxNode(mid+1, end, left, right, index*2+1);

        Tree result = new Tree();
        result.min = Math.min(l_child.min, r_child.min);
        result.max = Math.max(l_child.max, r_child.max);
        return result;
    }


    static class Tree {
        int min;
        int max;

        public Tree() {
            this.min = Integer.MAX_VALUE;
            this.max = Integer.MIN_VALUE;
        }
    }
}