문제 분석
문제에 대해 설명하자면 랜덤으로 나열된 수를 정렬하기 위해서 한 숫자를 맨 앞이나 뒤로 보낼 수 있을 때, 최소 이동횟수를 구하는 문제이다.
그리디 알고리즘으로 문제를 풀기 위해서 어떤 숫자를 앞이나 뒤로 보내는 게 최선의 선택인지 한참을 고민해봤는데 도저히 안될 것 같아서 풀이를 찾아보았다.
Key idea
결론부터 말하면 이 문제는 최장 증가 부분수열의 변형으로, 가장 길게 연속된 배열의 길이를 찾는 문제로 변형이 가능하다.
그 이유는 가장 적은 횟수로 어떤 숫자를 이동하여 정렬하기 위해서는 이미 정렬된 숫자들을 제외한 나머지 숫자들만 움직이면 최소횟수로 정렬이 가능하다. 이때 정렬되지 않은 숫자들은 연속된 배열의 길이를 늘리는 순서로만 이동하면 되기 때문에 최소 이동횟수는 단순히 전체 길이에서 정렬된 수열의 길이를 뺀 값이 된다.
예를 들어 [2,5,6,1,3,4]가 주어졌을 때, 가장 길게 연속되는 배열은 [2,3,4]이고, 나머지[5,6,1]을 1->5->6순서로 이동하면 정렬이 완료된다.
원본수열 최장증가연속수열
[2,5,6,3,1,4] [2,3,4]
(1)-> [1,2,5,6,3,4] [1,2,3,4]
(5)-> [1,2,6,3,4,5] [1,2,3,4,5]
(6)-> [1,2,3,4,5,6] [1,2,3,4,5,6]가장 간단하게 최장 증가 연속수열을 찾는 방법은 이중 반복문을 사용하여 모든 경우를 찾는 것이다. 하지만 이 문제에서는 N이 1,000,000개이므로 시간초과가 발생한다. 따라서 효율적으로 답을 찾기 위해서는 Greedy와 dp 두 가지 알고리즘을 사용할 수 있다.
Solution
Greedy
먼저 각 숫자들의 위치(인덱스)를 저장한 pos를 만든다. pos는 증가수열을 찾는동안 숫자의 위치를 찾기 위해 lookup 테이블로 사용된다. 그 다음 모는 숫자를 돌아가면서 증가수열을 찾는데, 연속된 수열을 찾아야하므로 current에 현재 숫자를 담으면 다음 숫자는 current+1이 되고, pos를 참고하여 current가 current+1보다 앞에 있으면 수열에 추가하고 current를 갱신한다. 이 과정을 반복하여 최종적으로 가장 긴 연속된 수열의 길이를 찾고, 전체 수열의 길이에서 빼주면 최소 이동횟수를 구할 수 있다.
n = int(sys.stdin.readline())
line = list(map(int, sys.stdin.readline().strip().split(" ")))
# Greedy
pos = [0 for _ in range(n+1)]
for i in range(n):
pos[line[i]] = i
max_count = 0
for i in range(n):
current = line[i]
count = 1
while current + 1 <= n and pos[current] < pos[current + 1]:
count += 1
current += 1
max_count = max(max_count, count)
print(n - max_count)DP
dp알고리즘으로는 문제를 좀 더 간단하게 해결할 수 있다. [2,5,6,1,3,4]라는 수열에서 4로 끝나는 연속수열([2,3,4])는 3으로 끝나는 연속수열([2,3])의 길이보다 항상 1이 크기 때문에 아래와 같은 점화식으로 각 숫자로 끝나는 연속수열의 길이를 구하면 된다.
d[n] = d[n-1] + 1이를 구현하기 위해 i로 끝나는 연속수열의 길이를 저장하는 lis를 0으로 초기화하고, 수열을 앞에서부터 탐색하면서 각 숫자에 대해 점화식을 적용한 다음 lis의 최댓값을 구하면 그 길이가 가장 긴 연속수열의 길이가 된다.
n = int(sys.stdin.readline())
line = list(map(int, sys.stdin.readline().strip().split(" ")))
# Dp
lis = [0 for _ in range(n+1)]
for i in range(n):
current = line[i]
lis[current] = lis[current-1] + 1
max_count = max(lis)
print(n - max_count)