[Python] Queue 예제 (Josephus)

 

1부터 N까지 차례대로 줄을 섰을 때,

맨 앞에 선 사람만 들여보내주고 그 다음 순서인 사람은 제일 뒤로 보내는 특이한 줄서기가 있습니다.

 

예를 들어,

N=6인 경우, 123456 이 순서대로 줄을 서있을 것입니다. 이때 제일 먼저 1이 입장하고 남은 순서는 23456이 됩니다. 2는 두 번째 순서이므로 제일 뒤로 보내서 34562가 됩니다. 다시 3이 입장하여 4562가 되고, 4가 두 번째 순서이므로 5624가 됩니다. 5가 입장하고 246, 2가 입장하고 64, 6이 입장하여 4, 마지막으로 4가 입장하게 됩니다. N이 주어질 때 제일 마지막으로 입장하는 숫자를 계산하는 프로그램을 작성하세요.

 

 

test.python

assert test_problem_queue(2) == 2
assert test_problem_queue(3) == 2
assert test_problem_queue(4) == 4
assert test_problem_queue(5) == 2
assert test_problem_queue(6) == 4
assert test_problem_queue(7) == 6

 

 

 

 

practice.python

from collections import deque  # deque 모듈을 불러오기 

def test_problem_queue(num):
    # 1부터 num까지의 숫자로 deque를 초기화합니다.
    deq = deque([i for i in range(1, num + 1)])
    
    # deque에 원소가 하나만 남을 때까지 반복합니다.
    while len(deq) > 1:
        # deque의 첫 번째 원소를 제거합니다. (첫 번째 사람이 제거됨)
        deq.popleft()
        # 이제 첫 번째 원소를 제거한 후, 새로운 첫 번째 원소(다음 사람)를 deque의 끝으로 이동시킵니다.
        deq.append(deq.popleft())
    
    # 마지막으로 남은 원소(사람)의 번호를 반환합니다.
    return deq.popleft()