[백준] 2164번 - 카드2 (파이썬)

https://www.acmicpc.net/problem/2164

2164번: 카드2

[코드]

처음에는 python list의 내장함수로 풀었다.

N = int(input())
queue = [i for i in range(1, N + 1)]

while len(queue) > 1:
    queue.pop(0)
    queue.append(queue.pop(0))
print(queue[0])

그랬더니, 시간초과가 발생하였다.

그래서 동일한 알고리즘을 deque 를 이용해 풀었더니 통과하였다.

from collections import deque

N = int(input())
queue = deque([i for i in range(1, N + 1)])

while len(queue) > 1:
    queue.popleft()
    queue.append(queue.popleft())
print(queue[0])

 

다음의 참고사이트에 따르면 

1. append와 pop의 경우에는 List와 Deque 둘 다 Time Complexity가 O(n)으로 별차이가 없음

2. appendleft와 popleft의 경우에 Deque가 훨씬 빠름

https://poorman.tistory.com/412

[Time Complexity] Python - Deque vs List performance comparison (append, appendleft, pop, popleft)

결론) deque 를 쓰자.