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

문제 링크

---

1. 문제 풀이

수열의 길이 $N$ 이 최대 $100,000$, 주어진 구간의 최솟값과 최댓값을 구하는 쿼리의 수 $M$ 이 최대 $100,000$ 인 문제로 쿼리 당 $O(\log{N})$ 의 시간복잡도로 해결할 수 있는 세그먼트 트리를 활용하면 해결할 수 있다. 구간의 최솟값과 최댓값을 구하며 변경 쿼리가 없다는 점에서 희소 테이블을 활용해도 해결할 수 있다.

---

2. 코드

1. 세그먼트 트리 [Java]

최솟값과 최댓값을 필드로 갖는 Node 클래스를 만들고 Node 객체에 대한 세그먼트 트리를 구현하는 방식으로 했다. merge 메서드로 상위 노드에서 구간의 대푯값을 갱신하게 해줬다. 항등원은 최솟값에는 가능한 최댓값, 최댓값에는 가능한 최솟값을 넣은 Node 객체가 된다.

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

public class Main {

    static final int MIN = 0;
    static final int MAX = 1_000_000_001;

    static class Node {
        int min;
        int max;

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

    static class SegmentTree {
        int n;
        Node[] tree;

        public SegmentTree(int[] arr) {
            this.n = arr.length - 1;
            this.tree = new Node[4 * n];
            init(arr, 1, 1, n);
        }

        void init(int[] arr, int node, int start, int end) {
            if (start == end) {
                tree[node] = new Node(arr[start], arr[start]);
                return;
            }

            int mid = (start + end) / 2;

            init(arr, node * 2, start, mid);
            init(arr, node * 2 + 1, mid + 1, end);
            tree[node] = merge(tree[node * 2], tree[node * 2 + 1]);
        }

        Node merge(Node a, Node b) {
            return new Node(Math.min(a.min, b.min), Math.max(a.max, b.max));
        }

        String query(int left, int right) {
            Node res = query(1, 1, n, left, right);
            return res.min + " " + res.max;
        }

        Node query(int node, int start, int end, int left, int right) {
            if (left > end || right < start) return new Node(MAX, MIN);
            if (left <= start && end <= right) return tree[node];

            int mid = (start + end) / 2;

            Node leftRes = query(node * 2, start, mid, left, right);
            Node rightRes = query(node * 2 + 1, mid + 1, end, left, right);
            return merge(leftRes, rightRes);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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[1 + N];
        for (int i = 1; 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, b)).append("\n");
        }

        System.out.println(sb);
    }
}

2. 희소 테이블 [Java]

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

public class Main {

    static final int LOG = 20;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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());
        }

        int[] lg = new int[1 + N];
        for (int i = 2; i <= N; i++) {
            lg[i] = lg[i / 2] + 1;
        }

        int[][] stMin = new int[LOG][N];
        int[][] stMax = new int[LOG][N];
        System.arraycopy(arr, 0, stMin[0], 0, N);
        System.arraycopy(arr, 0, stMax[0], 0, N);

        for (int k = 1; k < LOG; k++) {
            for (int i = 0; i + (1 << k) <= N; i++) {
                stMin[k][i] = Math.min(stMin[k - 1][i], stMin[k - 1][i + (1 << (k - 1))]);
                stMax[k][i] = Math.max(stMax[k - 1][i], stMax[k - 1][i + (1 << (k - 1))]);
            }
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken()) - 1;
            int b = Integer.parseInt(st.nextToken()) - 1;

            int k = lg[b - a + 1];
            sb.append(Math.min(stMin[k][a], stMin[k][b - (1 << k) + 1])).append(" ")
                    .append(Math.max(stMax[k][a], stMax[k][b - (1 << k) + 1])).append("\n");
        }

        System.out.println(sb);
    }
}

3. 세그먼트 트리 [C++]

최솟값과 최댓값을 pair 로 관리하는 세그먼트 트리를 구현하는 방식으로 했다. merge 메서드로 상위 노드에서 구간의 대푯값을 갱신하게 해줬다. 항등원은 최솟값에는 가능한 최댓값, 최댓값에는 가능한 최솟값을 넣은 pair 객체가 된다.

#include <bits/stdc++.h>
using namespace std;

constexpr int MIN = 0;
constexpr int MAX = 1000000001;

struct SegTree {
    int n;
    vector<pair<int, int>> tree;

    SegTree(int n) : n(n), tree(4 * n) {
    }

    void init(const vector<int>& arr, int node, int start, int end) {
        if (start == end) {
            tree[node] = {arr[start], arr[start]};
            return;
        }

        int mid = (start + end) / 2;

        init(arr, node * 2, start, mid);
        init(arr, node * 2 + 1, mid + 1, end);
        tree[node] = merge(tree[node * 2], tree[node * 2 + 1]);
    }

    pair<int, int> merge(pair<int, int> a, pair<int, int> b) {
        return {min(a.first, b.first), max(a.second, b.second)};
    }

    pair<int, int> query(int node, int start, int end, int left, int right) {
        if (left > end || right < start) return {MAX, MIN};
        if (left <= start && end <= right) return tree[node];

        int mid = (start + end) / 2;

        pair<int, int> leftRes = query(node * 2, start, mid, left, right);
        pair<int, int> rightRes = query(node * 2 + 1, mid + 1, end, left, right);
        return merge(leftRes, rightRes);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<int> v(n);
    for (int& x : v) cin >> x;

    SegTree tree(n);
    tree.init(v, 1, 0, n - 1);

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;

        pair<int, int> res = tree.query(1, 0, n - 1, a - 1, b - 1);
        cout << res.first << ' ' << res.second << '\n';
    }
}

4. 희소 테이블 [C++]

#include <bits/stdc++.h>
using namespace std;

constexpr int LOG = 20;
constexpr int MAXN = 100000;

int a[MAXN];
int stMin[LOG][MAXN];
int stMax[LOG][MAXN];
int lg[1 + MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> a[i];

    for (int i = 2; i <= n; i++) {
        lg[i] = lg[i / 2] + 1;
    }

    for (int i = 0; i < n; i++) {
        stMin[0][i] = a[i];
        stMax[0][i] = a[i];
    }

    for (int k = 1; k < LOG; k++) {
        for (int i = 0; i + (1 << k) <= n; i++) {
            stMin[k][i] = min(stMin[k - 1][i], stMin[k - 1][i + (1 << (k - 1))]);
            stMax[k][i] = max(stMax[k - 1][i], stMax[k - 1][i + (1 << (k - 1))]);
        }
    }

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;

        int k = lg[b - a + 1];
        int mn = min(stMin[k][a], stMin[k][b - (1 << k) + 1]);
        int mx = max(stMax[k][a], stMax[k][b - (1 << k) + 1]);
        cout << mn << ' ' << mx << '\n';
    }
}

---

3. 풀이 정보

1. 세그먼트 트리 [Java]

언어	시간	메모리	코드 길이
Java 11	760 ms	172076 KB	2537 B

2. 희소 테이블 [Java]

언어	시간	메모리	코드 길이
Java 11	668 ms	83976 KB	1664 B

3. 세그먼트 트리 [C++]

언어	시간	메모리	코드 길이
C++ 17	80 ms	5544 KB	1590 B

4. 희소 테이블 [C++]

언어	시간	메모리	코드 길이
C++ 17	64 ms	18428 KB	1070 B

---