Codeforces Round #813 (Div. 2) - Sort Zero 링크
(2022.10.19 기준 Difficulty *1100)
(Never cheat)

문제

n개의 양의 정수가 들어 있는 배열 a가 있고, 어떤 정수 x를 선택하여 ai = x인 모든 ai를 0으로 만들 수 있는 작업을 할 수 있다면, 배열을 감소하지 않는 순서로 정렬하기 위한 최소 작업 수

알고리즘

배열을 순서대로 훑으면서 감소하는 순서일 경우 앞 원소를 0으로 만드는 작업을 반복해야 한다.

풀이

기본적으론 뒤에서부터 훑으면서 비내림차순이 되게끔 작업을 해주면 된다.
0 <= ai <= n 이므로

make_zero = [False] * (n + 1)

이렇게 수를 0으로 만들었는지 판별할 배열을 만들고
비내림차순이 아니면 x = ai인 x에 대해 make_zero[x] = True로 해주고,
수를 비교할 땐, make_zero를 통해 0으로 만들어진 수인지 판별하여 비교해 나가면 된다.
여기서 끝일까..?
일단 위에서 말한대로 [1, 3, 2, 3, 4]를 예시로 들어보겠다.
뭔가 이상하지 않은가?
중간에 2가 있어서 이 배열은 비내림차순이 아니게 되었다.

그렇다. 중간에 3을 0으로 만들 때, 3이 마지막으로 나온 위치로 이동하여 다시 체크를 시작해야 하는 것이다.
이렇게 그림처럼 [1, 3, 2, 3, 4]의 배열의 최소 작업 수는 3이 된다.

결국은, 모든 특정 수에 대해 제일 마지막으로 나오는 위치(인덱스)를 저장해놓아야 하는 것이다.

코드

import sys; input = sys.stdin.readline

def solve():
    n = int(input())
    a = list(map(int, input().split()))

    if n == 1: # n이 1이면 0 출력
        print(0)
        return

    idx = [-1] * (n + 1) # 특정 수가 제일 마지막으로 나오는 위치
    for i in range(n):
        idx[a[i]] = i

    make_zero = [False] * (n + 1) # 특정 수를 0으로 만들었는지 판별
    i = n - 2 # 마지막 인덱스 - 1 위치부터 차례대로 내려감
    answer = 0 # 작업 수
    while i >= 0: # i가 0 이상인 동안
        # a[i]와 a[i + 1]을 비교해야 한다.
        # 만약 0으로 만들어진 수라면 0으로 저장하자.
        front = 0 if make_zero[a[i]] else a[i]
        back = 0 if make_zero[a[i + 1]] else a[i + 1]

        if front > back: # 만약 a[i]가 더 크다면 0으로 만들어서 배열이 오름차순이 되게끔 만들어야 한다.
            make_zero[front] = True # x = a[i]인 x를 0으로 만든다.
            answer += 1 # 작업 수는 1 증가
            i = idx[front] # 현재 위치는 0으로 만든 수가 마지막으로 나오는 위치로 이동해야 한다.
            if i == n - 1: # 만약 마지막 인덱스라면 -1 해주자.
                i -= 1
        else:
            i -= 1
    print(answer)


for _ in range(int(input())):
    solve()

여담

간단해보이지만 상당히 어려운 문제였다.
이게 difficulty 1100이라니..
백준으론 골드 5~3 정도 되는 듯?