(Python) - BOJ(1158번) : 요세푸스 문제

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

1158번: 요세푸스 문제

---

• 해설 : 

N명의 사람이 원을 이루면서 앉아있다고 할 때, 순서대로 K번째 사람을 제거한다. 모든 사람이 제거될 때까지 K번째 사람을 계속 제거한다. 이 때, 제거되는 사람들의 순서를 요세푸스 순열이라고 한다.

N과 K가 주어질 때 요세푸스 순열을 찾는 문제이다.

 

 

---

• 풀이 :

사람이 원형으로 앉아있는 모습을 구현하기 위해 원형 큐를 사용하였다. 실제로 구현한 것은 아니지만 비슷한 기능을 하게끔 구현하였는데 방법은 다음과 같다.

 

1. K번 만큼 queue의 popleft()값을 append()해준다. 

2. popleft()한 값을 정답 배열에 넣어준다. 

 

이 작업을 반복 수행하면 K번째 사람을 지속적으로 제거하는 요세푸스 순열을 구할 수 있다.

 

 

 

---

• 소스코드 : 

 

import sys
input = sys.stdin.readline
from collections import deque
 
if __name__ == '__main__':
    N,K = map(int,input().split())
    arr = deque([i for i in range(1,N+1)])
    ans = []
    while arr:
        for _ in range(K-1):
            arr.append(arr.popleft())
        ans.append(str(arr.popleft()))
    print("<",", ".join(ans),">",sep = '')