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

문제 설명

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

문제 풀이

• 세그먼트 트리를 이용하여 풀이하였다.
• 구간의 최대, 최소를 O(n)으로 탐색하며 풀면 당연히 시간초과가 발생한다.
• 구간의 최소값을 저장하는 세그먼트 트리와, 구간의 최대값을 저장하는 세그먼트 트리를 만들어 각각 O(logn)의 시간복잡도로 최솟값, 최댓값을 계산해준다.

소스 코드 (JAVA)

import javax.swing.text.Segment;
import java.io.*;
import java.util.*;

class Main {
    public static int N, M;
    public static int[] arr;
    public static int[][] qArr;
    public static BufferedWriter bw;
    public static BufferedReader br;

    public static class SegmentTree{
        private int[] tree;
        private boolean type;    //false: 최소 트리, true: 최대 트리

        public SegmentTree(int n, boolean type) {
            this.type = type;
            double height = Math.ceil(Math.log(n)/Math.log(2)) + 1;
            long nodeCnt = Math.round(Math.pow(2, height));
            tree = new int[Math.toIntExact(nodeCnt)];
        }

        //세그먼트 트리의 노드값 초기화
        int init(int[] arr, int node, int start, int end) {
            int mid = (start + end) / 2;
            if (start == end) return tree[node] = arr[start];
            else {
                if (type) return tree[node] = Math.max(init(arr, node*2, start, mid), init(arr, node*2+1, mid+1, end));
                else return tree[node] = Math.min(init(arr, node*2, start, mid), init(arr, node*2+1, mid+1, end));
            }
        }

        int cal(int node, int start, int end, int left, int right) {
            //범위 벗어나는 경우
            int mid = (start + end) / 2;
            if (end < left || right < start) {
                if (type) return Integer.MIN_VALUE;
                else return Integer.MAX_VALUE;
            }
            else if (left<=start && right >= end) return tree[node];
            else {
                if (type) return Math.max(cal(node*2, start, mid, left, right), cal(node*2+1, mid+1, end, left, right));
                else return Math.min(cal(node*2, start, mid, left, right), cal(node*2+1, mid+1, end, left, right));
            }
        }
    }

    public static void input() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new int[N];
        qArr = new int[M][2];
        for (int i = 0; i < N; i++)
            arr[i] = Integer.parseInt(br.readLine());
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            qArr[i][0] = Integer.parseInt(st.nextToken()) - 1;
            qArr[i][1] = Integer.parseInt(st.nextToken()) - 1;
        }
    }

    public static void main(String[] args) throws IOException {
        input();
        SegmentTree minSeg = new SegmentTree(N, false);
        SegmentTree maxSeg = new SegmentTree(N, true);
        minSeg.init(arr, 1, 0, N-1);
        maxSeg.init(arr, 1, 0, N-1);
        //결과 출력
        for (int i = 0; i < M; i++) {
            bw.write(minSeg.cal(1, 0, N-1, qArr[i][0], qArr[i][1])
                        + " " + maxSeg.cal(1, 0, N-1, qArr[i][0], qArr[i][1]) + "\n");
        }
        bw.flush();
    }
}