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

https://www.acmicpc.net/problem/2357

2357번: 최솟값과 최댓값

 

 

[ 문제풀이 ]

 

이 문제를 풀기 전에 다음 글을 읽고 오시면 좋습니다!!

https://rudalsd.tistory.com/51?category=1073064 

[ 자료구조 ] 세그먼트 트리 (Segment Tree)

 

일반적인 세그먼트 트리와는 다르게 최솟값과 최댓값을 저장해야 하므로 node라는 struct를 만들어서 각각의 최댓값과 최솟값을 저장할 수 있게 합니다. 그리고 자식 노드 중 왼쪽 노드와 오른쪽 노드의 최댓값과 최솟값을 각각 비교해 최댓값 중 더 큰 수를 현재 노드의 최댓값에 저장하고, 최솟값 중 더 작은 수를 현재 노드의 최솟값에 저장합니다.

 

세그먼트 트리를 만들고 나서는 범위를 입력받아 현재 노드가 구하고자 하는 범위에 완전히 포함된다면 현재 노드를 리턴해주고, 일부만 포함한다면 범위를 쪼개서 왼쪽과 오른쪽으로 재귀 호출을 합니다. 만약 구하고자 하는 범위에 완전히 포함되지 않는다면 최댓값은 0, 최솟값은 1111111111을 리턴해주면 됩니다.

 

[ 소스 코드 ]

#include<iostream>
#include<vector>
#include<cmath>
 
using namespace std;
 
struct node {
    int max;
    int min;
};
 
int N, M;
int arr[100001];    //입력받은 정수를 저장할 배열
vector<node> segTree;    //segment tree
 
node makeTree(int curNode, int start, int end)        //segment tree 만들기
{
    if (start == end) {        //리프 노드일 때
        return segTree[curNode] = { arr[start],arr[start] };
    }
 
    int mid = (start + end) / 2;
    node left = makeTree(curNode * 2, start, mid);    //왼쪽 자식 노드
    node right = makeTree(curNode * 2 + 1, mid + 1, end);    //오른쪽 자식 노드
    return segTree[curNode] = { max(left.max, right.max), min(left.min, right.min) };    //각 노드에 최솟값과 최댓값 저장
}
 
node findTree(int curNode, int start, int end, int sidx, int eidx)
{
    if (start > eidx || end < sidx) {    //구하고자 하는 범위를 완전히 벗어났을 때
        node cur = { 0,1111111111 };
        return cur;
    }
    if (start >= sidx && end <= eidx) {    //구하고자 하는 범위에 완전히 포함될 때
        return segTree[curNode];
    }
 
    int mid = (start + end) / 2;        //구하고자 하는 범위에 일부 포함될 때
    node left = findTree(curNode * 2, start, mid, sidx, eidx);        //왼쪽 자식 노드
    node right = findTree(curNode * 2 + 1, mid + 1, end, sidx, eidx);    //오른쪽 자식 노드
 
    node cur = { max(left.max,right.max), min(left.min,right.min) };
    return cur;
}
 
int main()
{
    cin >> N >> M;
 
    for (int i = 1; i <= N; i++) {
        scanf("%d", &arr[i]);
    }
 
    int size = (1 << (int)(ceil(log2(N)) + 1));    //segment tree의 사이즈
    segTree.resize(size);
    makeTree(1, 1, N);        //segment tree 만들기
 
    for (int i = 0; i < M; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        node ans = findTree(1, 1, N, a, b);
        printf("%d %d\n", ans.min, ans.max);
    }
}