[Python Silver IV 2164] 카드2

https://www.acmicpc.net/problem/2164

2164번: 카드2

 

보유한 카드가 1부터 N까지이고 N은 입력으로 주어지고 정렬된 상태입니다.



카드가 한 장이 남을 때까지 밑의 조건들을 반복합니다.



제일 위에 있는 카드를 바닥에 버립니다.
그다음 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮깁니다.


예를 들면 N이 4이면 보유한 카드는 ( 1, 2, 3, 4 )입니다.

1번 동작. 1을 버립니다. ( 2, 3, 4 )

2번 동작. 2를 맨 밑으로 보냅니다. ( 3, 4, 2 )

이런 식으로 카드가 1장이 남을 때까지 실행하고 마지막 카드를 출력하면 됩니다.

이번 문제에서 보유한 카드를 앞뒤로 추가하고 뺼꺼기 때문에 Queue 보단 Deque를 사용하는게 시간복잡도 면에서 좋습니다.

[ 1 ~ 2 ] Deque를 불러와 선언해줍니다.

[ 4 ~ 5 ] N을 입력받아 Deque에 1부터 N까지 수를 넣어줍니다.

[ 7 ~ 10 ] 맨 앞의 숫자를 제거하기 위해 popleft를 하고, 그다음 숫자를 Deque 뒤에 추가한 후 다시 한번 popleft 를 실행해줍니다. 이 행동을 Deque의 길이가 1이 될 때까지 반복해줍니다.

 

from collections import deque
Deq = deque()

for i in range(1, int(input())+1):
    Deq.append(i)
    
while len(Deq) != 1:
    Deq.popleft()
    Deq.append(Deq[0])
    Deq.popleft()

print(Deq[0])