Codeforces Round 656 (Div. 3) - Make It Good 링크
(2023.04.17 기준 Difficulty *1200)

문제

길이가 n인 배열 a가 주어지고, 앞이나 뒤에서 원소 하나씩 뽑아 나열하여 비내림차순으로 만들고자 한다. 이를 위해 제거해야 하는 a의 접두사 배열의 최소 길이를 출력.

알고리즘

전형적인 그리디

풀이

생각을 해보자. 앞이나 뒤에서 원소 하나씩 뽑아야 하고 비내림차순이 되어야 한다. 그리고 접두사 배열을 제거해야 하므로, 앞에서부터 잘라나가야 한다.
만약, 증가하다가 감소하는 구간이 있다면? 아무 문제 없다. 비내림차순의 순서대로 앞이나 뒤부터 존재하기 때문. 하지만, 감소하다가 증가하는 구간이 있다면? 문제가 있다. 그 구간 중간에 비내림차순의 첫번째가 존재하기 때문에 앞이나 뒤에서 원소를 뽑지 못한다.

두번째 예제를 그림으로 나타내면이와 같다.
앞에서부터 순서대로 살펴보자.
3번째에서 4번째는 증가한다. 하지만 앞에 1번째에서 2번째는 감소했다. 이 구간은 감소하다가 증가했기 때문에 제일 마지막으로 감소하는 안소까지만 제거해주자. 이 구간에선 1번째까지만 제거해주면 감소하다가 증가하는 구간이 없어진다.
5번째에서 6번째는 증가한다. 하지만 4번째에서 5번째는 감소했다. 그러므로 4번째까지는 제거해야 한다.

요약하자면, 증가하는 구간이 있을 때, 마지막으로 감소했으며 제거하지 않은 구간이 있다면 거기까지 제거해주면 된다.
위의 과정을 구현해주면 된다.

코드

• C++

#include <bits/stdc++.h>
using namespace std;

int n, result, last_down, a[200000];

void solve(){
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];

    result = last_down = 0; // 제거해야 하는 접두사 배열의 최소 길이, 마지막으로 감소했던 구간의 인덱스
    for (int i = 0; i < n - 1; i++){
        if (a[i] > a[i + 1]) // 감소하면 저장
            last_down = i + 1; // 0_based-index 이므로 +1을 해서 저장
        else if (a[i] < a[i + 1] && last_down) // 증가하며 마지막으로 감소했던 구간이 있다면
            result = last_down, last_down = 0; // 그 구간까지 제거해야 한다.
    }
    cout << result << '\n';
}

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

    int t;
    cin >> t;
    while (t--) solve();
}

• Python

import sys; input = sys.stdin.readline

for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))

    result = last_down = 0 # 제거해야 하는 접두사 배열의 최소 길이, 마지막으로 감소했던 구간의 인덱스
    for i in range(n - 1):
        if a[i] > a[i + 1]: # 감소하면 저장
            last_down = i + 1 # 0_based-index 이므로 +1을 해서 저장
        elif a[i] < a[i + 1] and last_down: # 증가하며 마지막으로 감소했던 구간이 있다면
            result = last_down # 그 구간까지 제거해야 한다.
            last_down = 0
    print(result)