[BOJ] 2357번 | 최솟값과 최댓값 (C++)

🔗문제 보러가기

2357번: 최솟값과 최댓값

 

👨‍💻풀이 과정

 

세그먼트 트리(Segment Tree) 첫 입문 문제로 풀었습니다. 첫 시도고, 조금 변형된 문제인지라 결국 다른 분들의 풀이를 참고하여 풀었지만, 세그먼트 트리라는 개념과 어느정도 친숙해진 그런 계기가 아니었나 싶습니다.

 

백준 문제를 풀면서 느낀 거지만, 다양한 알고리즘 문제들을 접해볼 수 있다는 게 되게 좋은 것 같습니다. 아직 접해보고 풀어봐야 할 문제들이 많지만 하나씩 천천히 해봐야죠. 풀이 과정을 적는 구간인데 제 느낀점을 적고 있었네요.

 

튜플(Tuple)을 가질 수 있는 pair<int, int>를 활용하여 최솟값과 최댓값을 가지도록 만들었고, vector<pair<int, int>>를 통해 세그먼트 트리를 만들었습니다. 구간 합을 빠르게 구하기 위한 세그먼트 트리 소스 코드가 일반적인데, 이 문제는 덧셈을 하는 것이 아니기 때문에 최솟값과 최댓값을 골라주는 로직으로 작성해주면 됩니다.

 

✏️ 소스 코드 및 결과

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;
using Data = pair<int, int>;    // <min, max>

#define FAST_IO ios::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
#define INF 1000000001

vector<Data> SegmentTree;
vector<int> Array;

int CreateMinSegmentTree(int node, int start, int last)
{
    if (start == last)
        return SegmentTree[node].first = Array[start];

    int mid = (start + last) / 2;
    int leftChild = node * 2, rightChild = node * 2 + 1;

    int leftChildMinInteger = CreateMinSegmentTree(leftChild, start, mid);
    int rightChildMinInteger = CreateMinSegmentTree(rightChild, mid + 1, last);

    return SegmentTree[node].first = min(leftChildMinInteger, rightChildMinInteger);
}

int CreateMaxSegmentTree(int node, int start, int last)
{
    if (start == last)
        return SegmentTree[node].second = Array[start];

    int mid = (start + last) / 2;
    int leftChild = node * 2, rightChild = node * 2 + 1;

    int leftChildMaxInteger = CreateMaxSegmentTree(leftChild, start, mid);
    int rightChildMaxInteger = CreateMaxSegmentTree(rightChild, mid + 1, last);

    return SegmentTree[node].second = max(leftChildMaxInteger, rightChildMaxInteger);
}

int FindMinInteger(int node, int start, int last, int left, int right)
{
    if (last < left or right < start)
        return INF;
    
    if (left <= start and last <= right)
        return SegmentTree[node].first;
    
    int mid = (start + last) / 2;
    int leftChild = node * 2, rightChild = node * 2 + 1;

    int leftMinInteger = FindMinInteger(leftChild, start, mid, left, right);
    int rightMinInteger = FindMinInteger(rightChild, mid + 1, last, left, right);

    return min(leftMinInteger, rightMinInteger);
}

int FindMaxInteger(int node, int start, int last, int left, int right)
{
    if (last < left or right < start)
        return -INF;
    
    if (left <= start and last <= right)
        return SegmentTree[node].second;
    
    int mid = (start + last) / 2;
    int leftChild = node * 2, rightChild = node * 2 + 1;

    int leftMaxInteger = FindMaxInteger(leftChild, start, mid, left, right);
    int rightMaxInteger = FindMaxInteger(rightChild, mid + 1, last, left, right);

    return max(leftMaxInteger, rightMaxInteger);
}

int main()
{
    FAST_IO
    int N, M;
    cin >> N >> M;

    Array.resize(N);
    for (int i = 0; i < N; i++)
        cin >> Array[i];
    
    int treeHeight = static_cast<int>(ceil(log2(N)));
    int treeSize = 1 << (treeHeight + 1);

    SegmentTree.resize(treeSize);
    CreateMinSegmentTree(1, 0, N - 1);
    CreateMaxSegmentTree(1, 0, N - 1);

    int from, to;
    for (int i = 0; i < M; i++)
    {
        cin >> from >> to;
        int minInteger = FindMinInteger(1, 0, N - 1, from - 1, to - 1);
        int maxInteger = FindMaxInteger(1, 0, N - 1, from - 1, to - 1);

        cout << minInteger << " " << maxInteger << "\n";
    }

    return 0;
}