7570. 줄 세우기

업데이트 시간 : 2024-02-20 15:17:04 +0000

[Gold III] 줄 세우기 - 7570

문제 링크

성능 요약

메모리: 224564 KB, 시간: 400 ms

분류

다이나믹 프로그래밍, 그리디 알고리즘

제출 일자

2024년 2월 21일 00:16:42

문제 설명

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

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

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

예를 들어, 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)

위의 예에서는 세 명의 어린이를 제일 앞이나 제일 뒤로 보내 번호순서대로 줄을 세웠다. 그리고 두 명 이하의 어린이를 제일 앞이나 제일 뒤로 보내는 방법으로는 번호순서대로 줄을 세울 수 없다. 그러므로 이 경우에는 최소한 세 명의 어린이를 이동하여야 번호순서대로 줄을 세울 수 있다.

이 문제는 처음에 줄서있는 상태에서 위 방법을 이용해서 번호순서대로 줄을 세울 때 앞이나 뒤로 보내는 어린이 수의 최솟값을 찾는 것이다.

입력

입력은 2 개의 줄로 이루어져 있다. 첫 줄에는 어린이 수를 나타내는 정수가 주어진다. 둘째 줄에는 처음에 줄서있는 어린이들의 번호가 차례대로 주어진다. 주어진 번호들 사이에는 공백이 하나씩 들어있다. 단, 어린이 수는 1이상 1,000,000이하의 정수로 제한되고, 어린이 수가 N이면 어린이들의 번호는 1부터 N까지의 정수이다.

출력

입력에서 주어진 어린이들의 줄에 대해 번호순서대로 줄을 세우기 위해 제일 앞이나 제일 뒤로 보내는 어린이 수의 최솟값을 출력해야 한다.

💡 Solutions

📄 줄 세우기.py

N = int(input())
nums = list(map(int, input().split()))
index = [-1] * (N + 1)

for idx, value in enumerate(nums):
    index[value] = idx # 각 번호가 현재 nums 배열에서 어디에 존재하는지 기록

longest = 0
cnt = 1

for i in range(1, N):
    if index[i] < index[i + 1]: # 번호 i가 nums 배열 내에서 번호 i + 1보다 앞에 존재한다면
        cnt += 1 # 오름차순의 길이가 1 증가했음을 기록
    else:
        cnt = 1
    longest = max(longest, cnt) # 지금까지 기록한 최장 길이를 갱신

# 번호 배열의 전체 길이에서 1씩 차이나는 가장 긴 오름차순의 길이를 제거
print(N - longest if N != 1 else 0) # N = 1이면 움직일 필요가 없다.
            
'''
좀 어지럽긴 한데, 정리를 해보겠다. 문제의 예시를 보면
문제의 핵심은 오름차순이 되어버린 정렬은 옮길 필요가 없다는 것이다
먼저 간단한 예시를 살펴보자.
2
1 2와

2 
2 1의 경우를 살펴보자면

각각
[-1, 0, 1] 
[-1, 1, 0]이다.

1번 케이스는 1번과 2번이 정 방향으로 있기 때문에 움직일 필요가 없다.
카운팅했던 가장 긴 오름차순은 1(기본) + 1 이며
총 갯수의 2 - 2 = 0

2번 케이스는 2번과 1번이 역방향으로 있기 때문에 움직여야한다.
카운팅했던 가장 긴 오름차순은 1(기본) + 0 이며
이동시킬 횟수는 2, 혹은 1을 한번 옮긴
총 갯수의 2 - 1 


이제 
5
5 2 4 1 3
를 보자

이런식으로 나와있다.
index 리스트는 
[-1, 3, 1, 4, 2, 0] 로 리스트 업 될 것이다. ([ 0, 1, 2, 3, 4, 5]의 위치에 대한 정보를 기록)

2번이 3번보다 앞에 있기 때문에 이동이 필요없다
즉 카운팅 되는 가장 긴 오름차순은 1(기본) + 1

오름차순 된 것을 제외하고 하나씩 이동

총 갯수 5 - 2 = 3

한 예제를 더 들어보겠다.
7
3 5 2 6 1 7 4

이동 시킬 횟수는
4를 맨 앞으로
3을 맨 앞으로
2를 맨 앞으로
1을 맨앞으로
4회가 될 것이다.

이게 어떻게 되냐면,
index 리스트는 
[-1, 4, 2, 0, 6, 1, 3, 5] 로 리스트 업 될 것이다. 
일단 3은 4보다 앞에있다.
즉 카운팅 되는 가장 긴 오름차순은 1(기본) + 1 = 2
그런데 4(6번째)가 5(첫번째)보다 뒤에 있기 때문에 이건 다시 고려해보아야한다.
cnt 를 1로 바꾼다.

그다음은 다시 반복이다 1+1+1 = 3 이 나오고, 이게 가장 큰 오름차순이다.
이후 총 갯수 7 - 3 = 4 가 나온다.
'''   