[BOJ 2357 // C++] 최솟값과 최댓값

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 2357번 문제인 최솟값과 최댓값이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/2357

2357번: 최솟값과 최댓값

이 문제 또한 세그먼트 트리(segment tree)의 구현을 연습하기 위해 풀어본 문제이다.

단, 이 문제에서는 중간에 값을 갱신할 필요는 없기 때문에 조금 더 입문하기에 좋은 문제이지 않았나 싶다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <cmath>
using std::cin; using std::cout;
using std::min; using std::max;

int arr[100001];
int minsegtree[400001];
int maxsegtree[400001];

int minseg(int L, int R, int segIndex) {
    if (L == R) minsegtree[segIndex] = arr[L];
    else minsegtree[segIndex] = min(minseg(L,(L+R)/2,segIndex*2),minseg((L+R)/2+1,R,segIndex*2+1));
    return minsegtree[segIndex];
}

int minquery(int L, int R, int queryL, int queryR, int segIndex) {
    if (queryL <= L && R <= queryR) return minsegtree[segIndex];
    if (R < queryL || queryR < L) return 1000000001;
    return min(minquery(L, (L + R) / 2, queryL, queryR, segIndex * 2), minquery((L + R) / 2 + 1, R, queryL, queryR, segIndex * 2 + 1));
}

int maxquery(int L, int R, int queryL, int queryR, int segIndex) {
    if (queryL <= L && R <= queryR) return maxsegtree[segIndex];
    if (R < queryL || queryR < L) return -1;
    return max(maxquery(L, (L + R) / 2, queryL, queryR, segIndex * 2), maxquery((L + R) / 2 + 1, R, queryL, queryR, segIndex * 2 + 1));
}

int maxseg(int L, int R, int segIndex) {
    if (L == R) maxsegtree[segIndex] = arr[L];
    else maxsegtree[segIndex] = max(maxseg(L, (L + R) / 2, segIndex * 2), maxseg((L + R) / 2 + 1, R, segIndex * 2 + 1));
    return maxsegtree[segIndex];
}

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

    int N, M; cin >> N >> M;
    for (int i = 1;i <= N;i++) {
        int x; cin >> x;arr[i] = x;
    }
    minseg(1, N, 1);
    maxseg(1, N, 1);
    for (int i = 0;i < M;i++) {
        int a, b; cin >> a >> b;
        cout << minquery(1, N, a, b, 1) << ' ' << maxquery(1, N, a, b, 1) << '\n';
    }
    return 0;
}