11866번 - 요세푸스 문제 0(python3)

문제 링크 : www.acmicpc.net/problem/11866

11866번: 요세푸스 문제 0

정말 오랜만에 백준 문제를 풀어서 올립니다. 요세푸스 수열(문제)은, 플라비우스 요세푸스라는 로마 시대의 역사가가 살기 위해... 머리를 굴린 경험으로부터 만들어진 문제입니다. 나무위키나, 영어 위키피디아에 자세한 썰이 있으니 궁금하면 한 번 찾아보세요!

 

정수 n, k가 주어질 때(n>k), n명의 사람이 원형으로 앉아있고, k번째 사람을 탈락시킵니다. n, k = 7, 3이면 요세푸스 수열은 3, 6, 2, 7, 5, 1, 4가 됩니다. 다음 예시에서 빨간색 볼드체 숫자가 탈락되는 숫자입니다.

 

1 2 3 4 5 6 7 (1-2-3)
1 2 3 4 5 6 7 (4-5-6)
1 2 3 4 5 6 7 (7-1-2)
1 2 3 4 5 6 7 (4-5-7)
...

이번에는 deque를 사용해서 풀어보도록 합시다. 그냥 list를 사용해도 되지만, list.pop(0)보다 deque.popleft()가 훨씬 빠르니 이를 이용해봅시다.

from collections import deque

n, k = map(int, input().split())
que = deque(range(1, n+1))

print("<", end="")
while que:
    for _ in range(k-1): #k-1번째까지는 살려둠
        que.append(que.popleft())
    print(que.popleft(), end="") #k번째 원소를 뺌
    if que:
        print(", ", end="")
print(">")

#다음 문제는 이 코드로 해결 가능
#11866번 - 요세푸스 문제 0
#1158번 - 요세푸스 문제

위 예시대로 n, k = 7, 3이면 queue의 1, 2번째 원소는 맨 뒤로 보내고(popleft - append), 3번째 원소는 popleft만 수행하여 제거합니다. 이를 queue가 비어있을 때까지 반복하면 요세푸스 수열 순서대로 원소를 출력할 수 있습니다. 스택오버플로우에 요세푸스 수열 문제를 특정 조건에서 O(klogn)에 풀 수 있는 답변이 있다는데, 궁금하신 분은 조금 더 찾아보셔도 좋을 것 같습니다.

 

백준에 요세푸스 문제가 다양하게 있는데, 본 문제와 1158번 문제까지는 위 코드로 풀립니다. 그 다음부터는 시간 초과 또는 메모리 초과가 뜨네요. 더 효율적인 방법으로 접근해야 나머지 문제도 풀 수 있을 것 같습니다.