🥸 문제 분석
1부터 N의 번호를 갖는 어린이가 N명 주어진다.
즉, 입력된 값에는 1부터 N까지의 번호가 하나씩 모두 존재한다.
하지만 번호가 정렬되어 있는 것은 아니고,
특정 번호들을 앞, 뒤로 보내서 정렬된 상태를 만들어야 한다.
어린이들을 앞, 뒤로 보내는 횟수를 최소로 하려면 어떻게 해야할까?
☝️ 문제 풀이
우선 N의 범위는 1,000,000 이하의 정수이기 때문에,
O(N^2)이상의 시간 복잡도로는 택도 없다는 것을 알 수 있다.
O(N) 이나 O(NlogN)의 시간복잡도로 해결할 수 있는 방법을 떠올려야 한다.
예제부터 살펴보자.
5
5 2 4 1 31을 맨 앞으로, 4를 맨 뒤로, 5를 맨 뒤로 보내면 정렬된 상태인 1 2 3 4 5 를 얻을 수 있다.
다른 예제를 살펴보자.
6
1 6 2 5 3 45를 맨 뒤로, 6을 맨 뒤로 보내면 정렬된 상태인 1 2 3 4 5 6을 얻을 수 있다.
두 예제에서 확인할 수 있는 점은,
어떤 번호가 어떤 위치에 있든 맨 앞이나 맨 뒤로 오름차순을 지키며 보낼 수 있다는 것이다.
즉, 그리디하게 문제 접근을 한다면, 오름차순은 어차피 무슨 수를 써서라도 만들 수 있기 때문에
이미 오름차순으로 정렬된 순서를 최대한으로 지키는 것이 이동 횟수를 최소화하는 방법임을 알 수 있다.
다만 주의할 것이 있다.
6
1 3 4 5 2 6위 예제에서 2만 옮긴다고 정렬된 순서를 만들 수 있을까? 절대로 불가능하다.
번호를 이동할 때 다른 번호 사이에 끼워넣을 수 있는게 아니라, 양쪽 끝에 보내는 것이기 때문이다.
2를 1과 3사이에 넣고 싶다면, 1도 같이 움직여 주어야 한다.
즉, 양쪽 끝에 보낸다는 조건 때문에 번호가 단순히 오름차순이기만 해서는 안 된다.
오름차순이면서 값이 1씩 차이나는 형태만 자리를 고정시킬 수 있다.
1 3 4 5 6 은 오름차순이긴 하지만, 1씩 차이나는 형태는 아니다.
3 4 5 6은 자리를 고정시킬 수 있지만, 1 2는 자리를 옮겨주어야 한다.
이제 코드를 어떻게 작성해야 될지 정해졌다.
값이 1씩 늘어나는 오름차순을 번호 내에서 찾으면 된다.
그걸 어떻게 찾을 수 있을까? 각 번호가 배열 내에서 갖는 인덱스를 활용할 수 있다.
5
5 2 4 1 3위 예제를 다시 돌아보면,
2는 배열에서 인덱스 1, 3 은 인덱스 4 이다.
두 인덱스를 비교했을 때, 3의 인덱스가 더 크므로,
3이 2보다 뒤에 존재하고 있음을 알 수 있다.
이러한 사실을 코드 작성에 적용해보자.
N = int(input())
nums = list(map(int, input().split())
idx = [-1] * (N + 1)
for i, v in enumerate(nums):
idx[v] = i # 각 번호가 현재 nums 배열에서 어떤 위치에 있는 지를 기록한다.위 코드로 1부터 N까지의 번호가 각각 nums 배열에서 어떤 인덱스를 갖는지 기록한다.
longest = 0
cnt = 1
for num in range(1, N):
if idx[num] < idx[num + 1]: # 번호 i가 nums 배열 내에서 번호 i + 1보다 앞에 존재한다면
cnt += 1 # 오름차순의 길이가 1 증가했음을 기록
else:
longest = max(longest, cnt) # 지금까지 기록한 최장 길이를 갱신
cnt = 1
# 번호 배열의 전체 길이에서 1씩 차이나는 가장 긴 오름차순의 길이를 뺀다.
print(N - longest if N != 1 else 0) # N = 1이면 움직일 필요가 없다.이제 idx 배열을 선형 탐색하면서, 오름차순이 유지되는 번호의 개수를 센다. (cnt 변수)
현재 번호의 바로 다음 번호가 nums 배열에서 더 뒤쪽 인덱스에 위치하는지 확인한다.
뒤쪽 인덱스에 위치한다면 오름차순이 유지되는 것이므로, cnt 변수에 1을 더해준다.
만약 그렇지 않다면 현재 번호부터 다시 오름차순을 기록한다. cnt 변수를 1로 바꾼다.
이렇게 선형 탐색해가면서 오름차순의 최대 길이를 찾고,
그것을 전체 길이인 N에서 빼면 번호 이동 횟수의 최솟값을 얻을 수 있다.
