문제 설명
요세푸스 문제는 다음과 같다.
1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.
N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.
풀이
반드시 큐로 풀 필요는 없지만 큐로 풀어본다.
collection의 덱(deque)을 이용해서 풀었다.
N이 7이고 K가 3이라면 초기 배열은 [1, 2, 3, 4, 5, 6, 7]
1을 지우고 뒤로 보내면 [2, 3, 4, 5, 6, 7, 1]
2를 지우고 뒤로 보내면 [3, 4, 5, 6, 7, 1, 2]
3을 지우고 뒤로 보내면 [4, 5, 6, 7, 1, 2, 3]
K가 3이므로 세 번째 순서인 3이 결과값에 들어갈 것이고, 사실 세 번째 순서일 경우에는 뒤로 보내면 안 된다. 순서대로 K번째 사람을 제거해야 하기 때문.
고로 세 번의 반복문을 돈 후 배열은 [4, 5, 6, 7, 1, 2]이 된다.
이걸 총 7번 반복하고 그때마다 세 번째일 때는 덱에서 popleft()한 값을 결과값에 넣으면 된다.
- 저번 에디터문제부터 이제부턴 정말 sys뿐이야를 결심했기 때문에
from sys import stdin
input = stdin.readline
이렇게 입력했더니 되려 시간초과 떠버림..
제출 코드
from collections import deque
n, m = map(int, input().split())
deq = deque()
for i in range(1, n + 1):
deq.append(i)
result = []
for i in range(n):
for j in range(m):
if j == m - 1 and deq:
result.append(deq.popleft())
elif j < m - 1 and deq:
f = deq.popleft()
deq.append(f)
print("<" + ", ".join(map(str, result)) + ">")