[백준] 줄세우기 7570 (파이썬)

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

난이도 : GOLD III

문제

방법: 줄 서있는 어린이 중 한 명을 선택하여 제일 앞이나 제일 뒤로 보낸다.

위의 방법을 사용할 때 어린이가 이동해서 빈자리가 생기는 경우에는 빈자리의 뒤에 있는 어린이들이 한 걸음씩 앞으로 걸어와서 빈자리를 메꾼다.
예를 들어, 5명의 어린이들에게 1부터 5까지의 번호가 주어져 있고, 다음과 같은 순서로 줄 서있다고 하자.

5 2 4 1 3

위 방법을 이용해서 다음과 같이 번호순서대로 줄을 세울 수 있다.

1번 어린이를 제일 앞으로 보낸다. (5 2 4 1 3 → 1 5 2 4 3)
4번 어린이를 제일 뒤로 보낸다. (1 5 2 4 3 → 1 5 2 3 4)
5번 어린이를 제일 뒤로 보낸다. (1 5 2 3 4 → 1 2 3 4 5)

문제해결

• 해결방법이 떠오르지 않아서 다른 블로그 글을 참고했다.
• 제일 앞이나 제일 뒤로 보내는 어린이의 수의 최솟값을 구하는 문제.
• 각 번호가 위치한 인덱스 리스트를 만든다.
• 이 인덱스 리스트에서 각 원소가 인접한 다음 원소보다 작으면 더 작은 값이 더 앞에 있는 것이므로 이동할 필요가 없다.

소스코드

import sys

input = sys.stdin.readline

n = int(input())

arr = [0] + list(map(int, input().split()))

count = [0] * (n+1) # arr에 존재하는 어린이의 번호가 몇번째있는지 나타내는 인덱스 리스트 ex) count[1] = arr에서 1번 어린이의 위치

for i in range(1,n+1):
  count[arr[i]] = i

cnt = 1
_max = -1
for i in range(1,n):
  if count[i] < count[i+1]:
    cnt += 1
    _max = max(cnt, _max)
  else:
    cnt = 1

print(n-_max)