(Python) 백준 2164번 - 카드 2

문제 링크 : https://www.acmicpc.net/problem/2164

2164번: 카드2

풀이

처음에는 단순히 list를 사용하여 풀이를 진행하였으나, 시간제한이 2초로 매우 짧아서 log(N)으로 삽입과 삭제를 진행하는 list로는 시간 초과가 발생할 수밖에 없었다. 그래서 상수 시간으로 조회, 삽입, 삭제가 가능한 deque를 사용하여 풀이를 진행하였다.

import sys
from collections import deque
# 1부터 n까지의 카드들을 deque를 사용하여 저장
arr = deque(range(1, int(sys.stdin.readline())+1))
while len(arr) > 1: # deque에 카드가 하나만 남을 때까지
    arr.remove(arr[0]) # 제일 위의 카드를 버리고
    arr.append(arr[0]) # 제일 위의 카드를 제일 아래로 
    arr.remove(arr[0]) # 옮긴다
print(arr[0])

 

※ 참고

Deque

https://lildev.tistory.com/40

(Python) 왜 deque를 사용하는가?