[백준/Python] 11866. 요세푸스 문제 0

✏️ 문제유형: 구현/ 큐

https://www.acmicpc.net/problem/11866

 

 

✏️ 풀이 

N명 중에서 K번째 사람을 계속해서 제거하는 문제이다. 

 

위의 예제로 이해를 해보면, 7명 중 3번째 사람을 계속 제거한다. 

 

앞에서 2명 pop-push하고 3번째 사람은 pop만 반복하면 되는데, 큐의 동작을 간단히 나열해보면 아래와 같다. 

 

1 2 3 4 5 6 7
pop-push: 1 2 / only pop: 3 
4 5 6 7 1 2 
pop-push: 4 5 / only pop: 6 
7 1 2 4 5
pop-push: 7 1 / only pop: 2
4 5 7 1 ... 반복 

 

이를 코드로 나타내면 아래와 같다. 

from collections import deque
n, k = map(int, input().split())
q = deque([i for i in range(1, n+1)])
ans = []
while q:
    for i in range(k-1):
        v = q.popleft()
        q.append(v)
    ans.append(q.popleft())
print("<", end='')
for i in range(n):
    if i < n-1:
        print(ans[i], end=', ')
    if i == n-1:
        print(ans[i], end='')
print(">")