[백준] 2357: 최솟값과 최댓값 - JAVA

in Algorithm on 자료 구조

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

풀이

구간이 주어지면 그 구간에서 최소, 최댓값을 찾아야 한다.

세그먼트 트리를 이용해 풀었다.

세그먼트 트리는 구간별로 값을 담아서 최댓값, 최솟값, 구간합 등 문제에 유용한 자료구조이다.

최소, 최대를 구해야 하기 때문에 Node라는 class를 만들어 최소, 최댓값을 담았다.

Node배열을 만들어 세그먼트 트리로 이용했다.

N개의 정수가 주어진다고 하면 트리 배열의 사이즈를 구하는 방법은 다음과 같다.

// 트리의 높이
int height = (int) Math.ceil(Math.log(arrSize) / Math.log(2));
// 트리의 노드 수
this.treeSize = (int) Math.pow(2, height + 1);

하지만 N * 4로 사이즈를 설정하면 충분하다.

init메서드로 배열을 입력받아 트리를 초기화했다.

재귀를 통해 start와 end가 같아지면 리프이므로 Node의 최소, 최댓값에 해당 인덱스의 배열의 값을 넣고

리프가 아닐 경우 자식 노드들을 이용해 최소, 최대를 찾아 새로운 Node에 넣었다.

find메서드에서는 구간을 줄여가면서 구해야 할 구간이 포함될 경우, 부분만 포함될 경우, 그 외의 경우를 나누어 값을 구했다.

메모리: 172592KB

시간: 812ms

언어: Java 11

코드

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

public class Main {
    static class Node {
        int min;
        int max;

        public Node(int min, int max) {
            this.min = min;
            this.max = max;
        }
    }

    static class SegmentTree {
        Node[] tree;

        public SegmentTree(int arrSize) {
            tree = new Node[arrSize * 4];
        }

        // 배열을 입력받은 후 트리 초기화
        public Node init(int[] arr, int node, int start, int end) {
            // 리프노드에 값을 넣고 반환한다
            if (start == end) {
                return tree[node] = new Node(arr[start], arr[start]);
            }

            // 리프노드가 아닌 경우 자식 노드로 들어간다
            Node a = init(arr, node * 2, start, (start + end) / 2);
            Node b = init(arr, node * 2 + 1, (start + end) / 2 + 1, end);
            return tree[node] = new Node(Math.min(a.min, b.min), Math.max(a.max, b.max));
        }

        // left ~ right 구간까지 합을 찾는다
        public Node find(int node, int start, int end, int left, int right) {
            // 구간에 포함되지 않을 경우
            if (left > end || right < start) {
                return new Node(Integer.MAX_VALUE, Integer.MIN_VALUE);
            }

            // 구하려고 하는 구간에 노드의 구간이 포함되어 있을 경우
            if (left <= start && end <= right) {
                return tree[node];
            }

            // 그 외의 경우 자식노드를 탐색
            Node a = find(node * 2, start, (start + end) / 2, left, right);
            Node b = find(node * 2 + 1, (start + end) / 2 + 1, end, left, right);
            return new Node(Math.min(a.min, b.min), Math.max(a.max, b.max));
        }
    }

    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[] arr = new int[N + 1];
        for (int i = 1; i < N + 1; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        SegmentTree seg = new SegmentTree(N);
        seg.init(arr, 1, 1, N);

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int left = Integer.parseInt(st.nextToken());
            int right = Integer.parseInt(st.nextToken());

            Node node = seg.find(1, 1, N, left, right);
            sb.append(node.min + " " + node.max).append("\n");
        }

        System.out.println(sb);
    }

}