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

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

 

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

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

---

1.  아이디어

 

구간에 대한 최솟값과 최댓값을 반복적으로 구해야한다는 점에서 세그먼트 트리를 활용하면 간단하게 해결할 수 있다.

---

2. 문제풀이

 

세그먼트 트리 클래스를 구현한 후 입력 값을 기반으로 세그먼트 트리를 생성해서 반복문으로 쿼리를 처리하는 방식으로 구현했다.

세그먼트 트리는 최솟값과 최댓값을 모두 처리하기 위해 minTree와 maxTree를 생성해서 각각 초기화했고 쿼리에 대해 minTree 쿼리와 maxTree 쿼리를 각각 처리해서 StringBuilder로 합쳐서 반환하는 방식으로 구현했다. 쿼리에서 구간이 벗어나는 경우 포함하지 않는다는 의미로 minTree는 Integer.MAX_VALUE를, maxTree는 Interger.MIN_VALUE를 반환해서 한다.

---

3. 코드

 

import java.io.*;
import java.util.*;

public class Main {

    private static class SegmentTree {
        private final int N;
        private final int[] minTree;
        private final int[] maxTree;

        public SegmentTree(int[] arr) {
            this.N = arr.length;
            this.minTree = new int[4 * N];
            this.maxTree = new int[4 * N];
            init(arr, 1, 0, N - 1);
        }

        private void init(int[] arr, int node, int start, int end) {
            initMinTree(arr, node, start, end);
            initMaxTree(arr, node, start, end);
        }

        private int initMinTree(int[] arr, int node, int start, int end) {
            if (start == end) return minTree[node] = arr[start];

            int mid = (start + end) / 2;
            int leftChild = 2 * node;
            int rightChild = 2 * node + 1;

            return minTree[node] = Math.min(initMinTree(arr, leftChild, start, mid), initMinTree(arr, rightChild, mid + 1, end));
        }

        private int initMaxTree(int[] arr, int node, int start, int end) {
            if (start == end) return maxTree[node] = arr[start];

            int mid = (start + end) / 2;
            int leftChild = 2 * node;
            int rightChild = 2 * node + 1;

            return maxTree[node] = Math.max(initMaxTree(arr, leftChild, start, mid), initMaxTree(arr, rightChild, mid + 1, end));
        }

        private String query(int left, int right) {
            return new StringBuilder()
                    .append(min(1, 0, N - 1, left, right))
                    .append(" ")
                    .append(max(1, 0, N - 1, left, right))
                    .toString();
        }

        private int min(int node, int start, int end, int left, int right) {
            if (left > end || right < start) return Integer.MAX_VALUE;

            if (left <= start && end <= right) return minTree[node];

            int mid = (start + end) / 2;
            int leftChild = 2 * node;
            int rightChild = 2 * node + 1;

            return Math.min(min(leftChild, start, mid, left, right), min(rightChild, mid + 1, end, left, right));
        }

        private int max(int node, int start, int end, int left, int right) {
            if (left > end || right < start) return Integer.MIN_VALUE;

            if (left <= start && end <= right) return maxTree[node];

            int mid = (start + end) / 2;
            int leftChild = 2 * node;
            int rightChild = 2 * node + 1;

            return Math.max(max(leftChild, start, mid, left, right), max(rightChild, mid + 1, end, left, right));
        }

    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

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

        SegmentTree tree = new SegmentTree(arr);

        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(tree.query(a - 1, b - 1)).append("\n");
        }

        bw.write(sb.toString());
        bw.flush();
    }
}

---

4. 후기