BOJ - 25400

백준 문제 링크
제자리

❓접근법

1. N장의 카드 왼쪽부터 각 인덱스에 맞는지 아닌지 판단
2. 인덱스는 i = 1로 설정하여, 인덱스에 맞으면 popleft 후 i를 1증가, 인덱스에 맞지 않으면 popleft 후 i를1증가, cnt 1증가

👌🏻코드

N = int(input())
a = list(map(int, input().split(" ")))

from collections import deque

cnt = 0

queue = deque(a)

i = 1
while queue:
    x = queue.popleft()
    
    if x != i:
        cnt += 1
    else:
        i += 1
        
print(cnt)

❌틀린 코드

N = int(input())
a = list(map(int, input().split(" ")))
i = 0
ans = 0
while i < len(a):
    
    if a[i] == a.index(a[i]) + 1:
        i += 1
    else:
        a.pop(a.index(a[i]))
        ans += 1
print(ans)

처음엔 위 코드로 제출했는데, 메모리와 시간을 초과해서 점수가 낮았다.
리스트는 시간복잡도가 O(N)이기 때문에 초과했던 것 같다.
그래서 시간복잡도가 O(1)로 낮은 deque 방식을 사용하니 제출에 성공했다.!!