[C++][백준 32752] 수열이에요?

문제

접근 방법

'L부터 R에 해당하는 부분이 정렬된 뒤에 A가 단조증가되는가?'를 확인하는 문제입니다.

L부터 R에 해당하는 부분을 정렬하는 방법으로 접근할 수 있습니다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N, L, R;
vector<int> A;

void input()
{
    ios::sync_with_stdio(0), cin.tie(0);

    cin >> N >> L >> R;
    --L;
    A = vector<int>(N);
    for (int &i : A)
    {
        cin >> i;
    }
}

bool solve()
{
    sort(A.begin() + L, A.begin() + R);

    for (int i = 0; i < N - 1; ++i)
    {
        if (A[i] > A[i + 1])
        {
            return false;
        }
    }

    return true;
}

int main()
{
    input();
    cout << solve();
    return 0;
}

풀이

L부터 R에 해당하는 범위를 정렬한 뒤 A가 차례대로 되어있는지 확인하여 해결할 수 있습니다.

정렬을 하지 않는 방법으로도 해결이 가능합니다.
어차피 L과 R 사이의 값은 순서대로 정렬될 운명입니다.
그렇기에 가장 왼쪽, 가장 오른쪽에 해당하는 값은 각각 최솟값, 최댓값입니다.
정렬을 하지 않고 L부터 R 범위에 최솟값, 최댓값을 찾아낸 뒤 가장 가까운 범위 밖의 수와 비교해 주면 됩니다.