[Queue] 요세푸스의 선물

큐: 한쪽 끝에서는 삭제만 가능하고 다른 한쪽 끝에서는 추가만 가능한 추상 데이터 타입

FIFO: First-In, First-Out

enqueue: 큐의 rear에 새로운 항목을 추가

dequeue: 큐의 front에 있는 항목을 제거

요세푸스는 N명의 제자들에게 선물을 주고 싶었으나, 선물이 하나 밖에 없었다.
그래서 다음과 같은 규칙을 가지고 게임을 해서 마지막으로 남은 한 사람에게만 선물을 주기로 했다.
모든 제자들은 무작위로 1번부터 N번까지 번호를 부여받아 번호 순서대로 시계방향으로 원을 이루어 앉는다.게임의 각 단계에서 시작 위치에 있는 제자는 1을 외치고, 시계방향으로 돌아가며 1씩 증가한 숫자를 외친다.t번째 단계에서 t^3, 즉, t의 세제곱수를 외치는 제자는 게임에서 탈락한다.t+1번째 단계에서는 탈락한 사람의 다음 사람이 1을 외치고 다시 t+1의 세제곱수를 외칠 때까지 게임을 진행한다.1단계에서는 1번 제자가 1을 외치기로 한다.
만약, 제자의 수가 N=3명이라면, 처음에 1 2, 3 의 순서로 원형으로 앉아 있다.
t=1 단계에서는 1번 제자가 1을 외치고, 1의 세제곱수는 1^3=1이므로 1번 제자가 탈락하고 2, 3 의 제자가 남는다.
t=2 단계에서는 2번 제자가 1을 외치고, 2의 세제곱수는 2^3=8이므로 3번 제자가 8을 외치게 되어 탈락한다.
t=3 단계에서는 2번 제자만 남았으므로, 2번 제자가 게임의 우승자가 되어 요세푸스의 선물을 받게 된다.

양의 정수 N이 주어졌을 때, 위 규칙에 따라 요세푸스의 선물을 받게 되는 제자의 번호를 출력하시오.

input
첫째 줄에 제자의 수 N이 주어진다.
2 <= N <= 50,000
[1] 6
[2] 10
[3] 50000
output
첫째 줄에 요세푸스의 선물을 받게 되는 제자의 번호를 출력한다.
[1] 6
[2] 8
[3] 14915

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

n = int(input())

def sol(n):
    circle, sequence = [i for i in range(1, n+1)], []
    j=0
    k=1
    while len(circle)>0:
        j=(j+(k**3)-1)%len(circle) # 원형 큐 사용
        sequence.append(circle.pop(j))
        k+=1
    return sequence[-1]

print(sol(n))