💡문제접근
- 위에서부터 사전 순으로 쌓으려면 몇 번을 움직여야하는지에 대한 문제다.
- 테스트케이스를 예로 들어 설명하면 다음과 같다.
💡테스트케이스
입력
3
3
2
1
출력
2
- 위의 테스트케이스에서 움직일 필요가 없는 책은 3번 책이다. 2번 책을 빼서 3번 책 위에 놓으면 [2, 3, 1] 순서가 될 것이고 1번 책을 빼서 2번 책 위에 놓으면 [1, 2, 3]으로 사전 순으로 정렬이 완료된다. 0번째 인덱스에 있는 값을 최댓값으로 두고 만약 최댓값보다 작거나 같은 값(문제에서 책의 호는 중복되지 않으므로 작은 값이라고 이해하면 됨)이 나오는 경우 횟수를 증가시키족 만약 최댓값보다 큰 값인 경우 이 때 (최댓값+1) 번호의 책이 그 아래에 위치하면 그대로 놔두고 아니라면 횟수를 증가시켜주는 방식으로 코드를 작성했다_
💡코드(메모리 : 45356KB, 시간 : 192ms)
import sys
input = sys.stdin.readline
N = int(input())
books = []
for _ in range(N):
books.append(int(input()))
Max = books[0]
cnt = 0
for book in books[1:]:
if book > Max:
if Max + 1 != book:
cnt += 1
Max = book
else:
cnt += 1
print(cnt)💡소요시간 : 28m
🐢