백준 17074번 - 정렬

https://www.acmicpc.net/problem/17074

하나의 수를 제외했을 때

오름차순으로 정렬된 경우가 몇개인지를 구하면 된다.

N이 10^5이기 때문에 O(N^2)으로 문제에 접근하여

하나를 제외했을 때마다 오름차순 정렬인지를 확인하면 시간초과에 걸리게 된다.

문제를 다시 읽어보면

오직 하나의 수를 제외했을 때 오름차순이 보장되어야한다.

즉, 두번이상 이전 숫자보다 다음 숫자가 감소를 하게 된다면 2개 이상의 수를 제외해야 하기 때문에 오름차순이 될 수 없다.

1)감소한 경우가 0인 경우 -> N가지

2)감소한 경우가 2이상인 경우 -> 0

3)감소한 경우가 1인 경우 -> 1또는 2가지

1번과 2번의 경우 항상 동일하지만

3번의 경우 상황에 따라 경우의 수가 달라지게 된다.

예를들어 1,5,3,4일 때

5를  제외한다고 하면 1,3,4가 되어 가능하게 되고

3을 제외한다고 하면 1,5,4가 되어 경우에 포함되지 않는다.

즉 감소하기 직전인 숫자 5의 순번을 i, 감소한 숫자 3의 순번을 i+1이라고 했을 때

arr[i-1]<=arr[i+1]이면 (i를 제외시) 경우의 수에 포함되고

arr[i]<=arr[i+2]이면 (i+1을 제외시) 경우의 수에 포함이 된다.

#include <iostream>
#include <vector>
using namespace std;
 
int main() {
 
    std::ios_base::sync_with_stdio(false);
    
    int N;
    cin >> N;
 
    vector<int> vec(N+2, 0);
    vec[0] = -1000000000;
    vec[N + 1] = 1000000000;
 
    int ans = 0;
    int cnt = 0;
    int before_dec = 0;
    int after_dec = 0;
    for (int i = 1; i <= N; i++) {
        cin >> vec[i];
 
        if (vec[i] < vec[i - 1]) {
            cnt++;
            before_dec = i - 1;
            after_dec = before_dec+1;
        }
    }
 
    if (cnt == 0)    ans = N;
    else if (cnt > 1)    ans = 0;
    else {
        if (vec[before_dec - 1] <= vec[after_dec])    ans++;
        if (vec[before_dec] <= vec[after_dec + 1])    ans++;
    }
    cout << ans << endl;
    return 0;
}