[Baekjoon/C++] 2357번 - 최솟값과 최댓값

[백준] Baekjoon Online Judge

문제로 이동

 

문제

N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 어려운 문제가 된다. 이 문제를 해결해 보자.

여기서 a번째라는 것은 입력되는 순서로 a번째라는 이야기이다. 예를 들어 a=1, b=3이라면 입력된 순서대로 1번, 2번, 3번 정수 중에서 최소, 최댓값을 찾아야 한다. 각각의 정수들은 1이상 1,000,000,000이하의 값을 갖는다.

 

입력

첫째 줄에 N, M이 주어진다. 다음 N개의 줄에는 N개의 정수가 주어진다. 다음 M개의 줄에는 a, b의 쌍이 주어진다.

 

출력

M개의 줄에 입력받은 순서대로 각 a, b에 대한 답을 최솟값, 최댓값 순서로 출력한다.

 

---

풀이

#include <iostream>
#include <vector>
using namespace std;

#define MAX 100001

int arr[MAX];
vector<pair<int, int>> tree(MAX * 4);

pair<int, int> init(int start, int end, int node);
pair<int, int> find(int start, int end, int left, int right, int node);

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

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

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

pair<int, int> find(int start, int end, int left, int right, int node) {
    if (left > end || right < start) return { 1000000000, 0 };

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

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

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

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

    int N, M;
    cin >> N >> M;

    for (int i = 1; i <= N; i++) cin >> arr[i];

    init(1, N, 1);

    while (M--) {
        int a, b;
        cin >> a >> b;

        pair<int, int> result = find(1, N, a, b, 1);
        cout << result.first << ' ' << result.second << '\n';
    }

    return 0;
}

 구간의 합/최솟값/최댓값 등이 저장된 트리를 사용하여 값을 구하는 시간을 단축하는 알고리즘인 세그먼트 트리 알고리즘을 사용하여 문제를 풀었다.

 

pair<int, int> init(int start, int end, int node) {
    // 자식이 없는 노드인 경우
    if (start == end) return tree[node] = { arr[start], arr[start] };

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

    // 좌측 자식 노드와 우측 자식 노드의 값에서 자기 자신의 값 구하기
    return tree[node] = { min(left.first, right.first), max(left.second, right.second) };
}

 세그먼트 트리를 초기화하는 함수이다. 해당 문제에서 구해야 하는 값은 구간의 최솟값과 최댓값으로 세그먼트 트리는 2가지의 정보를 저장해야 한다. 그렇기에 pair<int, int>를 사용하였다.

 

pair<int, int> find(int start, int end, int left, int right, int node) {
    // 현재 탐색한 범위가 찾으려는 범위 밖에 있을 때
    if (left > end || right < start) return { 1000000000, 0 };

    // 현재 탐색한 범위가 찾으려는 범위 안에 있을 때
    if (left <= start && end <= right) return tree[node];

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

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

 원하는 구간의 최솟값과 최댓값을 구하는 함수이다.

 1. 탐색한 범위(start, end)가 내가 찾으려는 범위의 밖에 있을 때 > 답에 영향을 주지 않는 값

 2. 탐색한 범위(start, end)가 내가 찾으려는 범위의 안에 있을 때 > 현재 탐색한 범위의 tree 값

 3. 그외 > 좌우로 나누어서 재귀 호출

 의 경우로 나누어서 다른 값을 return하도록 했다.