[백준] 2164 카드2(python)

백준 2164 카드 2

문제

N장의 카드가 있고 각각의 카드는 차례로 1부터 N까지의 번호가 1번 카드가 제일 위, N번 카드가 제일 아래인 상태로 놓여있다.

제일 위에 있는 카드를 바닥에 버린 후 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮기는 동작을 카드가 한 장 남을 때까지 반복하게 된다.

이때, 제일 마지막에 남게 되는 카드를 출력하는 것이다.

구현

처음에는 list를 이용했을 때는 시간 초과가 발생했다. 그래서 deque를 이용하자 시간 초과가 해결 되었다.

[코드 설명]
1. 1부터 N까지 deque에 넣는다.
2. 먼저 deque 제일 왼쪽에 있는 카드를 삭제한다.
3. 카드가 1개만 남았다면 반복문을 빠져나오고 그게 아니라면 제일 왼쪽에 있는 카드를 deque 뒤에 넣고 왼쪽에 있는 카드는 삭제한다.
4. 카드가 1장만 남을 때 까지 2,3번을 반복한다.
5. 마지막으로 남은 카드를 출력한다

[코드]

from collections import deque
n = int(input())
card=deque([i for i in range(n)])
while len(card) > 1 :
    card.popleft()
    if len(card) == 1 :
        break
    card.append(card[0])
    card.popleft()
print(card[0]+1)