[백준 2357] 최솟값과 최댓값

 

 풀고 나서야 알게 됐는데 세그먼트 트리 문제다. 세그먼트 트리 개념을 몰랐는데, 이렇게 하면 되지 않을까 싶어서 푼 방법이 세그먼트 트리를 이용하는 방법이었다. 

 

 문제를 처음 접했을 때, 대강 계산해도 직관적으로 떠오르는 알고리즘으로는 시간 복잡도가 너무 커지길래 브루트 포스 알고리즘을 그려놓고 조금씩 시간 복잡도를 깎아보기 시작했다. 큼직한 과정들을 그려두고, 어떤 부분을 줄일 수 있고, 어떤 부분이 무슨 짓을 해도 줄일 수 없는 부분이지 판단하는 건데, 이번 문제는 아무리 봐도 주어진 구간에 대해 최솟값과 최댓값을 구하는 O(n) 로직을 줄여야만 했다.

 

 그럴려면 일반적으로 생각해 볼 수 있는 것은, 전처리를 통해 이용하기 좋은 형태로 입력 값을 가공하는 것이다. 만약 모든 시작점과 끝점을 기준으로 최솟값과 최댓값을 미리 구해둘 수 있다면 O(1)만에 접근할 수 있겠지만, 정렬된 데이터도 아니니까 O(n^2)만큼 걸려 의미가 없었다. 메모리도 초과될 것이고.

 

지저분한 발상의 과정.. 나는 실제로 알고리즘 문제를 풀 때마다 그림판을 애용한다.

 

 그래서 분할 정복을 이용해볼까 하는 생각이 들었는데, 그렇다면 전체 구간에 대한 최소/최대, 그리고 그 구간을 절반으로 쪼갠 구간에 둘에 대한 각각의 최소/최대... 이런 식으로 전처리를 해두면 될 것 같았다. 전처리 비용도 계산해 보면 시간복잡도는 O(n log n)일테니까 충분했고, 공간 복잡도 문제도 최솟값과 최댓값을 나타내는 두 int를 노드로 하는 트리 형태고 완전 이진 트리 형태로 나타날 테니 2^h - 1일 테니까 충분해 보였다(h = ceil(log(n+1))). 

 

 전처리 이후에는, 분할 정복 형태로 트리를 탐색하면 될테니까 O(log n)만큼 걸릴 거고 m번 반복되어도 시간 복잡도는 널널해 보였다. 이후에는 그냥 단순히 생각한걸 코드로 옮겨서 구현했다. 트리의 사이즈는 최대 n 값은 100,000을 기준으로 계산해서 270,000 정도로 잡아주었는데, 나중에 찾아보니 공간을 4n정도로 할당하는 게 관행인 것 같았다. 

 완전 이진 트리 형태를 이용할 것이니까, 루트 노드의 인덱스를 1로 잡아서 좌, 우 자식 노드에 접근하기 편하게 했고, 이를 기반으로 트리 형성 및 탐색 함수도 작성했다.

 탐색할 때는, 3가지 케이스로 나누었는데, 실제 내가 구하려는 구간을 bound 값으로 주고, 현재 탐색 중인 구간이 bound 내에 있는지, 아니면 걸쳐 있는지, 아예 벗어나있는지에 따라 나누어 처리했다. bound 내에 있다면, 전처리해 둔 노드의 value를 그대로 리턴하면 되고, 아예 벗어나 있다면 min 값에 INF를, max 값에 0을 담아 리턴해 불필요한 탐색 및 값의 반영을 막는다. 만약 걸쳐있다면 절반으로 쪼개 탐색을 이어나가면 된다.

 

 세그먼트 트리를 모르고 풀어서, 배웠던 자료 구조와 알고리즘들을 토대로 추측해서 풀게 되었는데, 예상대로 돌아가는 것을 보았을 때 짜릿한 문제였다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#define INF 1000000001

using namespace std;

vector<pair<int, int> > minMaxTree(270000, {INF, 0}); // {min, max}
vector<int> numArr;

pair<int, int> makeTree(int l, int r, int ind) {
    if(l==r) {
        minMaxTree[ind] = {numArr[l], numArr[l]};
        return minMaxTree[ind];
    } else {
        int mid = (l+r)/2;
        pair<int, int> leftChild = makeTree(l, mid, ind*2);
        pair<int, int> rightChild = makeTree(mid+1, r, ind*2+1);
        minMaxTree[ind] = {min(leftChild.first, rightChild.first), max(leftChild.second, rightChild.second)};
        return minMaxTree[ind];
    }
}

pair<int, int> getMinMax(int l, int r, int ind, int lBound, int rBound) {
    if(l > rBound || r < lBound) return {INF, 0};
    if(l >= lBound && r <= rBound) return minMaxTree[ind];
    int mid = (l+r)/2;
    pair<int, int> leftMinMax = getMinMax(l, mid, ind*2, lBound, rBound);
    pair<int, int> rightMinMax = getMinMax(mid+1, r, ind*2+1, lBound, rBound);
    return {min(leftMinMax.first, rightMinMax.first), max(leftMinMax.second, rightMinMax.second)};
}

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

    int n, m;
    cin >> n >> m;
    numArr = vector<int>(n+1);
    for(int i=1; i<=n; i++) {
        cin >> numArr[i];
    }

    makeTree(1, n, 1);

    int left, right;
    for(int i=0; i<m; i++) {
        cin >> left >> right;
        pair<int, int> result = getMinMax(1, n, 1, left, right);
        cout << result.first << " " << result.second << "\n";
    }

}