[python/백준] 7570번: 줄 세우기

 

 

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

7570번: 줄 세우기

 

 

⭐ 문제

 

대한 어린이집에 올해 입학한 어린이들이 놀이터에 한 줄로 서있다. 모든 어린이들에게는 입학할 때 주어진 번호가 있고 모두 옷에 번호표를 달고 있다. 그런데 어린이들은 아직 번호 순서대로 줄을 잘 서지 못하므로 선생님이 다음과 같은 방법을 사용해서 번호순서대로 줄을 세우려고 한다.

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

위의 방법을 사용할 때 어린이가 이동해서 빈자리가 생기는 경우에는 빈자리의 뒤에 있는 어린이들이 한 걸음씩 앞으로 걸어와서 빈자리를 메꾼다.

예를 들어, 5명의 어린이들에게 1부터 5까지의 번호가 주어져 있고, 다음과 같은 순서로 줄 서있다고 하자.

 

5 2 4 1 3

 

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

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

 

 

 

⭐ 코드 분석

 

어린이 수를 입력받는 변수 N입력

 

배열을 출력하는 것이 아닌 숫자를 출력하는 것이므로 숫자만 세면 된다

 

숫자 값과 그 숫자가 배열되어있는 인덱스 값을 구하여 비교한 후 몇명의 어린이가 번호에 맞게 서있는지 하고 전체 어린이 숫자에서 빼기 

 

( 숫자가 인덱스 값에 맞게 위치해 있으면 증가 x)

 

 

 

/

 

 

 

 

⭐ 코드

 

n = int(input())
num = list(map(int, input().split()))
num.insert(0, 0)

result = [0 for _ in range(n + 1)]

for i in range(1, n + 1):
    result[num[i]] = i

cnt = 1
max_length = -1

for i in range(1, n):
    if result[i] < result[i + 1]:
        cnt += 1

        if cnt > max_length:
            max_length = cnt

    else:
        cnt = 1
print(n - max_length if max_length != -1 else 0)