백준 파이썬 2164번: 카드 2

www.acmicpc.net/problem/2164

2164번: 카드2

문제 유형: 자료 구조, 큐

 

# Solution 1 - 시간초과

from sys import stdin
n = int(stdin.readline())
cards = [i for i in range(1, n + 1)]
count = 1
left = []

while len(cards) != 1:
    if count%(2) == 1:
        del cards[0]
        count += 1

    else:
        cards.append(cards[0])
        del cards[0]
        count += 1
        
print(cards[0])

input()대신 sys.stdin.readline()를 사용했지만 결과는 여전히 시간 초과. 다른 접근법을 생각해보기로 했다.

 

# Solution 2

import collections

n = int(input())
cards_deque = collections.deque([i for i in range(1, n + 1)])

while len(cards_deque) != 1:
    cards_deque.popleft()
    cards_deque.rotate(-1)

print(cards_deque[0])

찾아보니 collections.deque 를 사용해야 하는 문제라고 한다. 이미 구현된 라이브러리를 통해 비교적 간단하게 작성할 수 있었다.