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

백준의 최솟값과 최댓값(2357) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

단순 반복문을 이용해서 매 연산마다 최솟값 최댓값을 구한다면 TLE가 발생하게 된다. 따라서 본인은 세그먼트 트리를 이용하는

방법으로 접근해 보았다.

먼저, 세그먼트 트리에 대해서 잘 모른다면 아래의 글을 읽고 오도록 하자.

[ 세그먼트 트리 알아보기(Click) ]

이 문제에서는 위에 링크를 걸어놓은 세그먼트 트리에 대한 설명을 해놓은 글과 약간 다르게 세그먼트 트리를 구현해 주어야 한다.

보통, 특정 구간에 대한 연산 결과를 노드에 저장해놓은 형태가 세그먼트 트리인데, 이 문제에서는 노드들에 최솟값과 최댓값을 저장해 주면 된다. 그래서 본인은 최솟값에 대한 세그먼트 트리와, 최댓값에 대한 세그먼트 트리 2개의 트리를 만들어서 해결해 주었다.

[ 소스코드 ]

#include<iostream>
#include<vector>
#include<cmath>
 
#define endl "\n"
using namespace std;
 
int N, M;
vector<int> Array;
vector<int> MinTree_Array;
vector<int> MaxTree_Array;
vector<pair<int, int>> Cmd;
 
int Min(int A, int B) { if (A < B) return A; return B; }
int Bigger(int A, int B) { if (A > B) return A; return B; }
 
void Input()
{
    cin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        int a; cin >> a;
        Array.push_back(a);
    }
    for (int i = 0; i < M; i++)
    {
        int a, b; cin >> a >> b;
        Cmd.push_back(make_pair(a, b));
    }
}
 
int Make_SegmentTree(int Node, int Start, int End, bool T)
{
    if (Start == End)
    {
        if (T == false)
        {
            return MinTree_Array[Node] = Array[Start];
        }
        else
        {
            return MaxTree_Array[Node] = Array[Start];
        }
    }
 
    int Mid = (Start + End) / 2;
    int Left_Result = Make_SegmentTree(Node * 2, Start, Mid, T);
    int Right_Result = Make_SegmentTree(Node * 2 + 1, Mid + 1, End, T);
 
    if (T == false)
    {
        MinTree_Array[Node] = Min(Left_Result, Right_Result);
        return MinTree_Array[Node];
    }
    else
    {
        MaxTree_Array[Node] = Bigger(Left_Result, Right_Result);
        return MaxTree_Array[Node];
    }
}
 
int Query(int Node, int Start, int End, int Left, int Right, bool T)
{
    if (Left > End || Right < Start)
    {
        if (T == false) return 2e9;
        else return -2e9;
    }
    if (Left <= Start && End <= Right)
    {
        if (T == false) return MinTree_Array[Node];
        else return MaxTree_Array[Node];
    }
 
    int Mid = (Start + End) / 2;
    int Left_Result = Query(Node * 2, Start, Mid, Left, Right, T);
    int Right_Result = Query(Node * 2 + 1, Mid + 1, End, Left, Right, T);
 
    if (T == false) return Min(Left_Result, Right_Result);
    else return Bigger(Left_Result, Right_Result);
}
 
void Solution()
{
    int Tree_Height = ceil(log2(N));
    int Tree_Size = (1 << (Tree_Height + 1));
    MinTree_Array.resize(Tree_Size);
    MaxTree_Array.resize(Tree_Size);
 
    Make_SegmentTree(1, 0, N - 1, false);
    Make_SegmentTree(1, 0, N - 1, true);
 
    for (int i = 0; i < Cmd.size(); i++)
    {
        int Index = Cmd[i].first - 1;
        int Index2 = Cmd[i].second - 1;
        
        int Min_Result = Query(1, 0, N - 1, Index, Index2, false);
        int Max_Result = Query(1, 0, N - 1, Index, Index2, true);
 
        cout << Min_Result << " " << Max_Result << endl;
    }
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
 
}