[파이썬] 2164번: 카드2

2164번: 카드2 (acmicpc.net)

2164번: 카드2

입력이 50만까지 주어지기 때문에 시간 초과에 유의하여 풀어야 한다.
처음에는 리스트로 해결했는데 답은 맞았지만 시간 초과가 발생하여 deque 라이브러리로 해결했다.

아래 페이지를 보면 deque의 삽입/삭제 연산 시간 복잡도는 O(1), 리스트는 O(n)이라 설명하고 있다.
리스트는 삽입/삭제 연산에서 비워진 곳을 메우기 위해, 혹은 새로 삽입된 값의 자리를 만들어 주기 위해 원소가 추가로 이동하지만 deque는 양방향 연결리스트로 관리되어 그렇지 않기 때문이다.

Deque in Python - GeeksforGeeks

혹시나 싶어 deque에 들어가는 리스트도 축약형으로 작성했는데 그게 큰 차이를 만들어내지는 않는 것 같다.

리스트로 푼 코드

import sys

n = int(sys.stdin.readline())
que = []

for i in range(1, n+1):
    que.append(i)

while len(que) > 1:
    que.pop(0)
    popped = que.pop(0)
    que.append(popped)

print(que[0])

deque 라이브러리로 푼 코드

import sys
from collections import deque

n = int(sys.stdin.readline())
que = deque([i for i in range(1, n+1)])

while len(que) > 1:
    que.popleft()
    popped = que.popleft()
    que.append(popped)

print(que[0])