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

 

11866번: 요세푸스 문제 0 (acmicpc.net)

11866번: 요세푸스 문제 0

• N명의 사람이 원을 이루며 앉아있음
• K번째 사람을 제거 → N명의 사람이 모두 제거될 때까지 계속 제거
• 원에서 사람들이 제거되는 순서 ↔ (N,K)-요세푸스 순열

💡 알고리즘

구현, 자료구조, 큐

💡 접근

[Python] 백준 #1966 프린터 큐 (tistory.com)

풀다가 이 문제가 생각나서 deque으로 수월하게 해결하였다.

→ while문으로 카운트를 세면서 조건을 확인하고,

• 맞다면 result에 저장하고 pop
• 아니라면 맨 뒤로 보내고 pop

💡 코드

from collections import deque

N, K = map(int, input().split())

dq = deque(x for x in range (1, N + 1))

cnt = 1
res = []

while dq :
    if cnt % K == 0 :
        cnt += 1
        res.append(dq[0])
        dq.popleft()
    else :
        cnt += 1
        dq.append(dq[0])
        dq.popleft()

print('<', end='')
for i in range(len(res)-1):
    print(res[i], end=', ')
print(res[-1], end='>')