list에서 pop(0)의 연산이 O(n)이라고 함.
그래서 python 공식 docs에서도 리스트는 큐로 쓰는 걸 권장하지 않는다고 함. 차라리 collections의 deque을 쓰라고 함.
deque
popleft, pop
append, appendleft
나머지 extend, extendleft, rotate은 O(k)의 시간 복잡도를 가짐
remove는 O(n)의 시간 복잡도를 가짐
마지막 한 장 남았으면 어차피 맨 뒤로 보내므로 그냥 return해 버리기의 의도로
cards.popleft() 다음으로 len(cards)==1을 검사해서 return해 주었으나,
N = 1의 경우 그렇게 되면 while문에서 영원히 못 빠져나와서 런타임에러 생김.
N = 1의 경우를 따로 빼 줌.
from collections import deque
def main():
N = int(input())
cards = deque(range(1, N+1))
if N == 1:
return 1
while(True):
# 맨 앞 장 바닥에 버리기
cards.popleft()
if len(cards) == 1:
return cards.pop()
# 다음 앞 장 맨 뒤로 보내버리기
top = cards.popleft()
cards.append(top)
print(main())