[c++][java][백준 2357] 최솟값과 최댓값

백준 2357번: 최솟값과 최댓값 [Gold 1]
https://www.acmicpc.net/problem/2357

2357번: 최솟값과 최댓값

문제 풀이

• 이 문제는 특정 구간의 최솟값과 최댓값을 찾는 문제로 완전 탐색으로 값을 찾게 되면 시간 초과에 걸리게 된다. 
• 구간 연산에 대한 문제는 세그먼트 트리(Segment Tree)를 생각할 수 있는데, 세그먼트 트리는 각 노드별로 일정 구간의 연산을 가지고 있는 트리를 말한다.

Segment Tree

• 위의 그림이 세그먼트 트리인데, 1번 노드는 0~9, 2번 노드는 0~4, 3번 노드는 5~9 등 각 노드별로 일정 구간에 대한 연산을 가지고 있는 것이다. 
• 위의 논리를 가지고 1번 노드는 0~9 구간의 최솟값과 최댓값, 2번 노드는 0~4 구간의 최솟값과 최댓값을 가지고 있도록 세그먼트 트리를 구현하여 문제를 해결하였다.
• 자바의 경우 Pair 구조체가 없기 때문에 class로 직접 구현했고, 트리 사이즈를 위한 log2(N)도 직접 구현해주었다. 트리 사이즈는 러프하게 N * 4를 하여 사용하기도 한다.

코드 (c++)

#include <cstdio>
#include <cmath>
#include <vector>

using namespace std;

#define MAX 1e9

vector<pair<int,int>> seg_tree;
int arr[100010];
int n, m;

pair<int,int> init(int node, int start, int end) {
    if(start == end)
        return seg_tree[node] = {arr[start], arr[start]};

    int mid = (start + end) / 2;
    pair<int,int> left = init(2*node, start, mid);
    pair<int,int> right = init(2*node+1, mid+1, end);

    return seg_tree[node] = {min(left.first, right.first), max(left.second, right.second)};
}

pair<int,int> solve(int node, int start, int end, int left, int right) {
    if(left > end || right < start) return {MAX, -MAX};
    if(left <= start && end <= right) return seg_tree[node];

    int mid = (start + end) / 2;
    pair<int,int> l = solve(2*node, start, mid, left, right);
    pair<int,int> r = solve(2*node+1, mid+1, end, left, right);

    return {min(l.first, r.first), max(l.second, r.second)};
}

int main() {
    scanf("%d %d", &n, &m);

    for(int i=0; i<n; ++i) {
        scanf("%d", &arr[i]);
    }

    int h = (int)ceil(log2(n));
    int ts = (1 << (h + 1));

    seg_tree.assign(ts, {0,0});

    init(1, 0, n-1);

    int left, right;
    for(int i=0; i<m; ++i) {
        scanf("%d %d", &left, &right);

        pair<int,int> res = solve(1, 0, n-1, left-1, right-1);

        printf("%d %d\n", res.first, res.second);
    }

    return 0;
}

실행 결과

코드 (Java)

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

// 백준 2357: 최솟값과 최댓값
// Segment Tree
public class Main {

    static int n, m;
    static Pair[] seg_tree;
    static int[] arr;
    static final int MAX = (int) 1e9;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        arr = new int[n];
        int h = (int) Math.ceil(log2(n));
        int ts = 1 << (1 + h);
        seg_tree = new Pair[ts];

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

        init(1, 0, n-1);

        int left, right;
        for(int i=0; i<m; ++i) {
            st = new StringTokenizer(br.readLine());

            left = Integer.parseInt(st.nextToken());
            right = Integer.parseInt(st.nextToken());

            Pair res = solve(1, 0, n - 1, left-1, right-1);
            System.out.println(res.min + " " + res.max);
        }
    }

    static Pair init(int node, int start, int end) {
        if(start == end) return seg_tree[node] = new Pair(arr[start], arr[start]);

        int mid = (start + end) / 2;
        Pair l = init(2*node, start, mid);
        Pair r = init(2*node+1, mid+1, end);

        return seg_tree[node] = new Pair(Math.min(l.min, r.min), Math.max(l.max, r.max));
    }

    static Pair solve(int node, int start, int end, int left, int right) {
        if(left > end || right < start) return new Pair(MAX, -MAX);
        if(left <= start && end <= right) return seg_tree[node];

        int mid = (start + end) / 2;
        Pair l = solve(2*node, start, mid, left, right);
        Pair r = solve(2*node+1, mid + 1, end, left, right);

        return new Pair(Math.min(l.min, r.min), Math.max(l.max, r.max));
    }

    static double log2(int num) {
        return Math.log(num) / Math.log(2);
    }

    static class Pair {
        int min;
        int max;

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

실행 결과