BOJ 2872 - 우리집엔 도서관이 있어

문제

BOJ 2872 - 우리집엔 도서관이 있어

1부터 N까지 번호가 매겨진 책이 무작위 순서로 놓여 있을 때, 아래에서 위로 1~N 순서가 되도록 정렬하기 위해 최소 몇 권을 빼서 다시 꽂아야 하는지 구하라.

입력

첫째 줄에 책의 수 N, 이후 N줄에 각 책의 번호가 아래에서 위 순서로 주어진다.

출력

빼서 다시 꽂아야 하는 최소 책의 수를 출력한다.

예제

풀이

이미 올바른 순서로 놓인 책들의 최대 부분 수열을 찾아 나머지를 이동한다.

1. 목표값을 N으로 설정하고 입력 리스트를 뒤에서부터 순회한다
2. 현재 책 번호가 목표값과 같으면 이 책은 제자리에 있으므로 목표값을 1 감소시킨다
3. 순회 후 남은 목표값이 이동해야 할 책의 수이다

핵심 아이디어: N부터 역순으로 이미 정렬된 연속 부분열은 그대로 두고, 나머지만 빼서 꽂으면 최소 이동이 된다.

코드

n, *r = map(int, open(0).read().split())
while r:
    n -= r.pop() == n
print(n)

복잡도

• 시간: O(N)
• 공간: O(N)