[BOJ:11866]요세푸스 순열

문제

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

[

11866번: 요세푸스 문제 0

첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000)

www.acmicpc.net

](https://www.acmicpc.net/problem/11866)

코드

import sys
from collections import deque

sys.stdin = open("input.txt")

N, K = map(int,sys.stdin.readline().rstrip().split())

check = [False]*(N+1)
check[0] = True

q = deque()
res = []
cnt = 0
for i in range(1,N+1):
    q.append(i)

while q:
    for i in range(K):
        num = q.popleft()
        if i == K-1:
            res.append(num)
        else:
            q.append(num)

print("<",end="")
for i in range(N-1):
    print(res[i],end="")
    print(", ",end="")
else:
    print(res[N-1],end="")
    print(">",end="")

문제해결방법

• 문제를 잘 읽어보면 원형탁자에서 K번째 사람을 제거하는 방식이다. 연속적으로 존재하면서 원형적으로 동작하는 자료구조는 큐가 있다.
• 문제에서 주어진 사람을 1부터 N까지 사람에 번호를 메겨 큐에 저장하고 저장된 큐에서 자료를 꺼내고 K번째 사람이 아니면 다시 큐에 집어 넣으면서(이때 큐에 다시 집어 넣는 행위가 맨뒤로 보내는 행위와 같다.큐는 입력시 가장 마지막에 들어가기 때문이다.) K번째 사람을 제거하면 된다. 그리고 제거한 값을 결과로 제출할 배열에 저장해주면된다.