[Queue] 카드 버리기

1번부터 N번까지 숫자가 적힌 카드가 1번 카드가 제일 위에, N번 카드가 제일 아래쪽에 오도록 순서대로 쌓여 있다.
이 카드 더미를 다음과 같은 규칙으로 한 장의 카드씩 버리고자 한다.
카드 더미의 가장 위에 있는 카드 한 장은 버린다.다음에는 제일 위에 있는 카드 한 장을 카드 더미의 가장 아래쪽으로 옮긴다.
위와 같은 규칙으로 카드를 하나씩 버릴때, 가장 마지막으로 버리게 되는 카드 번호를 출력하시오.
예를 들어, N=4의 경우, 카드 더미는 처음에 위에서부터 1, 2, 3, 4 순서로 쌓여 있다.
1을 버리고 2를 아래쪽으로 옮기면 카드 더미는 3, 4, 2 순서가 된다.
3을 버리고 4를 아래쪽으로 옮기면 카드 더미는 2, 4 순서가 된다.
2를 버리고 4를 아래쪽으로 옮기면 카드 더미는 4가 된다.
따라서 마지막으로 버리는 카드는 4번 카드이다.

Input
첫째 줄에 양의 정수 N이 주어진다.
1 <= N <= 10,000
6

7

10000

Output
첫째 줄에 가장 마지막에 버리게 되는 카드의 번호를 출력한다.
4

7

3616

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

n = int(input())

def sol(n, k):
    if n==1:
        return 1
    else:
        return (sol(n-1, k)+k)%n +1

print(sol(n, 1)-1)

# 풀이2
n = int(input())

stack = list(range(1,n+1))

while(len(stack) > 1) :
    stack.pop(0)
    stack.append(stack.pop(0))

print(stack[0])