[백준 2164] 카드2 with Python

문제 링크

www.acmicpc.net/problem/2164

2164번: 카드2

풀이

import sys
from collections import deque

dq = deque([x for x in range(1, int(sys.stdin.readline())+1)])
while len(dq) > 1:
    dq.popleft()
    dq.append(dq.popleft())
print(dq[0])

deque에 1부터 n까지 정수를 입력하고 카드를 빼고 옮기는 행위를 deque에 카드가 1장 남을 때까지 반복한다.

 

처음에 list로 풀려고 했다가 시간 초과가 났다. 파이썬의 list는 중간에 있는 요소를 pop할 때 시간복잡도가 O(n)이나, collections.deque는 시간복잡도가 O(1)이다. 앞으로는 문제를 읽을 때 어떤 자료구조가 필요한지 꼭 생각해 보아야겠다.