[백준] 11866 요세푸스 문제 0 파이썬 풀이 (큐, 덱)

 

코드

from collections import deque

n, k = map(int, input().split())

stack = deque([i for i in range(1, n+1)])
print("<", end="")
while len(stack) != 1:
    for _ in range(k-1):
        stack.append(stack.popleft())

    print(stack.popleft(), end=", ")
print(f"{stack.popleft()}>")

 

 

 

풀이

 

원래 이해가 안됐던 점은

만약에 7 7 이 입력되면

7번째 사람이 죽고 6명 남으면 어떡하지? 라고 생각했는데

그러면 계속 돌면서 7번째 사람을 죽이는 것이다

예를 들어 1 2 3 4 5 6 사람이 있으면 여기서 7번째는 1번이다

 

stack에 1부터 n번호까지 사람을 넣고

k번째 사람이 맨 왼쪽에 올때까지 stack에 맨 앞에 원소를 꺼내서 맨 뒤에 넣는다

7명이고 3번째 사람을 죽인다고 치면

1 2 3 4 5 6 7 에서

2 3 4 5 6 7 1 을 만들고

3 4 5 6 7 1 2 를 만들어서

맨 앞의 3을 없애면서 print를 한다

이렇게 계속 반복한다.