[BOJ 7570] 줄세우기

문제

[BOJ 7570] 줄세우기

처음에 줄서있는 상태에서 번호순서대로 줄을 세울 때 앞이나 뒤로 보내는 어린이 수의 최솟값을 찾기

구상

children 배열에서 오름차순으로 정렬된 어린이들 빼고는 다 위치 바꿔줘야함
즉 2,3(가장 긴 증가하는 수열) 빼고 1,4,5를 맨앞 또는 맨뒤로 보내야함

1. n번 어린이의 위치를 저장하는 idxs 배열 만들기
   (위 예제의 경우 idxs=[0, 3, 1, 4, 2, 0] 1번부터시작하기 때문에 idx[0]은 의미없는값)
2. idxs 배열에서 값이 증가하는 구간 중 가장 긴 구간의 길이 longest구하기

   idx[1]->idx[2] = 3->1 감소 탈락
   idx[2]->idx[3] = 1->4 증가 longest = 2
   idx[3]->idx[4] = 4->2 감소 탈락
   idx[4]->idx[5] = 2->0 감소 탈락
   longest = 2

3. N-longest(=3)가 답!

코드

import sys
input = sys.stdin.readline

N = int(input()) # 1<=어린이수<=1,000,000
children = list(map(int,input().split()))

idxs = [0]*(N+1)
for i in range(N):
    idxs[children[i]]=i

cnt = 1
longest = 0
for n in range(1,N):
    if idxs[n]<idxs[n+1]:
        cnt += 1
        if cnt>longest:
            longest = cnt
    else:
        cnt = 1
        
print(N-longest)