✔ 풀이를 위한 아이디어
- 덱(Deque) 모듈의 사용
✔ 코드
import sys
from collections import deque
N = int(sys.stdin.readline())
card = deque(range(1, N+1))
while len(card) > 1:
card.remove(card[0])
tmp = card.popleft()
card.append(tmp)
print(card[0])- 처음에는, 배열에 요소가 딱 1개 남을 때까지 계속해서 홀수번째에 있는 요소들 (index = 0, 2, 4..)을 지워나가는 방법을 생각했다. 그러나 이 방법으로는 시간복잡도를 줄일 수 없었다.
- 결국 구글링을 통해 python에 내장되어 있는 deque 모듈을 사용해야 한다는 것을 알게 되었고, 이를 활용하여 간단하게 풀었다.
✔ 관련 개념
- 자료구조 중 큐(Queue) 구조, 정확히는 양쪽에서 push와 pop을 할 수 있는 덱(Deque) 구조
https://codetorial.net/python/collections_deque.html
