문제 링크

문제 소개

해당 문제는 어떠한 수열을 제공받았을 때 1부터 M까지 정렬된 수로 전환하려면 최소 몇번 움직여야하는지 물어보는 문제이다.

문제 분석

해당 문제에서 최소로 움직여야하기 때문에, 어떠한 값이 제자리로 위치하는지 보다는 수열에서 증가하는 수들의 집합들 중 큰 집합을 고정해두고 그 외의 수들을 이동하면 최소 횟수를 구할 수 있을 것이다.

예를 들어 설명해보면 아래와 같다.

위와 같이 수열이 존재할 때, 순서대로 정렬하기 위해 가장 크고 증가하는 부분 수열을 아래와 같이 주황색으로 색칠하였고 이 수들을 고정할 것이다.

이렇게 3개의 수를 고정시킨 다음 중간중간에 수들을 원위치 시키면 4로 답이 된다.

이렇게 문제해결을 위해서는 Lis 알고리즘을 선행해야한다. Lis 알고리즘은 따로 포스팅으로 정리하였으니 궁금하면 아래의 링크를 참조하길 바란다.

Lis 알고리즘

정리하자면 Lis 알고리즘을 통해 증가하는 최대 부분 수열을 구한 다음 전체 수열의 개수에서 해당 부분 수열의 개수만큼 빼면 답이 될 것이다.

세세한 코드 리뷰는 위의 Lis 알고리즘 링크에서 가보면 알다시피, 비슷하기 때문에 궁금하다면 마찬가지로 위의 링크를 참조하길 바란다.

전체 코드

import sys


def lisWithBinarySearch1(M):
    arr = [int(input().rstrip('\n')) for _ in range(M)]
    dp = [arr[0]]
    for i in range(M):
        if arr[i] > dp[-1]:
            dp.append(arr[i])
        else:
            dp[bisect.bisect_left(dp, arr[i])] = arr[i]
    return len(dp)


def solution():
    input = sys.stdin.readline
    M = int(input().rstrip('\n'))
    print(M - lisWithBinarySearch1(M))


solution()