[Python3, 파이썬] 백준 2164 카드2

N = int(input())
stk = []
for i in range(N):
    stk.append(N-i)    
while stk:
    if len(stk) > 1:
        stk.pop()        
        stk.insert(0, stk.pop())
    else:
        print(stk.pop())

이렇게 풀었는데 시간 초과였다.

스택이라고 생각하고 만들었지만 실상은 배열이기 때문에 시간복잡도가 N^2이 넘는다.

2초 안에 절대 안풀림.

 

deque 모듈을 써보자.

from collections import deque

N = int(input())
dq = deque(range(1, N+1))

while len(dq) > 1 :
    dq.popleft()
    dq.append(dq.popleft())

print(dq.pop())

이렇게 하면 224ms 걸린다. 통과.