최솟값과 최댓값

알고리즘 구분 : 세그먼트 트리, 자료 구조

문제

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에 대한 답을 최솟값, 최댓값 순서로 출력한다.

예제 입력 1
10 4
75
30
100
38
50
51
52
20
81
5
1 10
3 5
6 9
8 10
예제 출력 1
5 100
38 100
20 81
5 81

문제 풀이

계속 세그먼트 트리 문제를 풀어보는 중이다.
이 문제는 어제 풀었던 10868. 최솟값 문제 풀이와 동일한 로직이다. 차이점은 최댓값도 존재한다는 것이다. 처음에는 pair<int, int> 자료형을 이용하여 first에는 최솟값을, second에는 최댓값을 저장하는 방식으로 구현해보고자 하였는데, 아직 실력이 부족해서 그런지 TLE를 받았다. TLE받게 된 원인에 대해서는 조금 더 고민해볼 필요가 있을 것 같다. 일단 TLE가 나왔기에, 최솟값을 위한 세그먼트 트리와 최댓값을 위한 세그먼트 트리를 별도로 구현하여 AC를 받았다. 구현 과정은 위 하이퍼링크 문제와 동일하다. 전체 배열을 순회하면서 탐색하는데 걸리는 시간복잡도가 매우 크기에, 이를 O(logN)으로 줄일 수 있는 세그먼트 트리를 생성하여 이를 순회하면서 찾아갈 수 있도록 하면 된다.

소스 코드

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"
#define MAX 100000

int n, m;
vector<int> v(100001, 0);
int maxTree[4 * MAX];
int minTree[4 * MAX];
int minInit(int start, int end, int node);
int maxInit(int start, int end, int node);
int findMin(int start, int end, int node, int left, int right);
int findMax(int start, int end, int node, int left, int right);

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

    cin >> n >> m;
    for(int i = 0; i < n; i++) {
        cin >> v[i];
    }

    minInit(0, n - 1, 1);
    maxInit(0, n - 1, 1);

    for(int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        cout << findMin(0, n - 1, 1, a - 1, b -1) << " " << findMax(0, n - 1, 1, a - 1, b- 1) << endl;
    }

    return 0;
}

int minInit(int start, int end, int node) {
    if(start == end) {
        return minTree[node] = v[start];
    }

    int mid = (start + end) / 2;
    return minTree[node] = min(minInit(start, mid, node * 2), minInit(mid + 1, end, node * 2 + 1));
}

int maxInit(int start, int end, int node) {
    if(start == end) {
        return maxTree[node] = v[start];
    }

    int mid = (start + end) / 2;
    return maxTree[node] = max(maxInit(start, mid, node * 2), maxInit(mid + 1, end, node * 2 + 1));
}

int findMin(int start, int end, int node, int left, int right) {
    if(left > end || right < start) return 1000000001;

    if(left <= start && end <= right) return minTree[node];
    
    int mid = (start + end) / 2;
    return min(findMin(start, mid, node * 2, left, right), findMin(mid + 1, end, node * 2 + 1, left, right));
}

int findMax(int start, int end, int node, int left, int right) {
    if(left > end || right < start) return 0;

    if(left <= start && end <= right) return maxTree[node];
    
    int mid = (start + end) / 2;
    return max(findMax(start, mid, node * 2, left, right), findMax(mid + 1, end, node * 2 + 1, left, right));
}

• 문제 출처 : https://www.acmicpc.net/problem/2357
• 해당 풀이는 백준에서 "맞았습니다!!" 판정을 받았습니다.