2164.py

# 카드2
# 시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
# 2 초 (추가 시간 없음)	128 MB	145958	76088	59010	50.963%

# 문제
# N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, 
# N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.

# 이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 
# 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.

# 예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 
# 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 
# 마지막으로 2를 버리고 나면, 남는 카드는 4가 된다.

# N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하는 프로그램을 작성하시오.

# 입력
# 첫째 줄에 정수 N(1 ≤ N ≤ 500,000)이 주어진다.

# 출력
# 첫째 줄에 남게 되는 카드의 번호를 출력한다.


# 문제 분석
# 큐의 개념을 이용한 문제
# front에 있는 카드를 가장 아래로 옮기는 동작은 큐의 선입선출을 이용해서 동작한다.

# 풀이 순서
# 1) popleft를 수행해 맨 앞 카드를 버림
# 2) 이어서 append를 수행해 맨 앞 카드를 맨 뒤로 옮김
# 3) 큐 크기가 1이 될 때까지 위 과정을 반복 후 큐에 남은 원소 출력


# 슈도코드
# n 카드 갯수, myQueue 카드 숫자를 저장할 큐

# for n 카드 갯수만큼 반복:
#     큐에 카드 저장

# while 카드가 1장 남을때까지:
#     맨 위 카드 버림, popleft()
#     맨 위 카드를 맨 아래로 옮김, poprleft() -> append()

# 마지막 남은 카드 출력


# Solutuon Code
from collections import deque
n = int(input())
myQueue = deque()

for i in range(1, n+1):
    myQueue.append(i)
    
while len(myQueue) > 1:
    myQueue.popleft()
    myQueue.append(myQueue.popleft())
    
print(myQueue[0])


# 해설
# 1. deque
# 파이썬에서 제공하는 모듈, double-ended queue의 줄임말
# 양쪽에서 데이터를 추가, 제거할 수 있는 자료구조
# 리스트와 비슷하지만, 양쪽에서 데이터를 관리할 수 있다는 점이 더욱 효율적

# 2. 주어지는 카드
# 첫 번째 for문에 의해서 myQueue에 1~n까지 숫자 카드가 저장됨
# --------------------
# 1 2 3 ...          n
# --------------------

# 3. popleft()의 기능
# 맨 앞에 있는 카드를 버림

# Q. popright()는 없나요?
# A. pop()이 똑같은 기능을 수행한다.
# 리스트에서 pop()의 기능을 생각하자. 맨 뒤에 있는 원소를 제거하는 기능이다.