[백준 17074번] 정렬 (C++)

문제링크 : https://www.acmicpc.net/problem/17074

17074번: 정렬

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int arr[100001];

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

    int N, cnt=0, idx=0;
    cin >> N;

    arr[0]=-1000000000;
    arr[N+1]=1000000000;

    for(int i=1; i<=N; i++)
    {
        cin >> arr[i];
    }

    for(int i=2; i<=N; i++)
    {
        if(arr[i-1] > arr[i]) 
        {
            cnt++;
            idx=i;
        }
    }

    
    if(cnt==0) cout << N; //감소하는 것이 없음 (정렬상태) (어떤 값이든 삭제 가능)
    else if (cnt > 1) cout << 0; //수를 하나만 버리기에 2개 이상 감소하면 정렬불가
    else
    {
        int result = 0;
        if(arr[idx-1] <= arr[idx+1]) result++; //현재 인덱스 값 삭제 확인
        if(arr[idx-2] <= arr[idx]) result++; //현재 인덱스의 바로 앞의 값 삭제 확인
        cout << result;
    }

    return 0;
}

경우의 수는 아래와 같이 3가지가 있다.

감소하는 값이 없다 : 정렬상태이므로 어떤 값이든 삭제 가능 (N 출력)
감소하는 값이 2개 이상 : 수를 하나만 버릴 수 있으므로 정렬 불가 (0 출력)
감소하는 값이 1개 : 조건에 따라 경우의 수가 1이나 2

여기서 문제가 되는 것은 감소하는 값이 1개인 경우이다.

감소하는 값의 idx를 저장하고, 현재 arr[idx]의 값을 삭제해야하는가?

아니면 바로 앞의 값(arr[idx+1])을 삭제해야하는가? 를 확인해줘야 한다.

 

예시로 1 2 3 1 4를 두면,

여기서 1을 삭제해야하는 것을 알 수 있다.

이를 위해서 감소하는 값인 1의 인덱스 위치를 저장하고, 해당 인덱스를 기준으로 바로 앞의 값이 바로 뒤의 값보다 작거나 같다면 정렬상태이므로 이러한 조건을 만족할때 경우의 수를 증가시킨다.

 

예시로 1 2 3 1을 두면,

여기서도 1을 삭제해야하는 것을 알 수 있지만 조금 다르다.

위에서 썼던 식대로 하면 arr[idx+1]의 값이 공석이므로 경우의 수가 증가하지 않는다.

따라서 이러한 경우를 위해 처음에 arr[N+1]의 값을 이 문제의 최대값인 1000000000로 초기화해줘서 이를 방지해준다.

 

예시로 1 3 2 3 4를 두면,

여기서 3을 삭제해야하는 것을 알 수 있다.

이러면 현재 idx 값의 앞에 있는 값을 삭제하는 것이므로 더 앞의 칸인 2칸 앞의 값이 현재 idx의 값보다 작거나 같은지 확인하며 정렬상태를 만족시킬수 있는지 확인한다.

 

예시로 4 3 4 5 6을 두면,

여기서 4를 삭제해야하는 것을 알 수 있다.

위에서 썼던 식대로 하면 arr[idx-2]의 값이 공석이므로 경우의 수가 증가하지 않는다.

따라서 이러한 경우를 위해 처음에 arr[0]의 값을 이 문제의 최소값인 -1000000000로 초기화해줘서 이를 방지해준다.

입력받을 때 arr[1]부터 입력받는 이유이기도 하다.