요세푸스 문제

백준 1158

• 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다.
• 순서대로 K번째 사람을 제거한다.
• 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다.
• 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다.

입출력

입력	출력
7 3	<3, 6, 2, 7, 5, 1, 4>

---

접근 방식

: 수를 늘여뜨려 놓고, 제일 첫번째에 오는 수만 출력할 수 있도록 구현.

• 제일 첫번째에 오는 수는 K번째 수이다. 따라서 해당 수가 첫번째에 오기까지 이전 원소들을 pop하고 리스트 뒤에 붙인다. -> 덱의 rotate(-1)을 사용할 수 있음
  • 자료구조 덱을 이용하여 구현.
• 이 과정을 리스트에 원소가 존재하는 동안 반복한다.
  
  
  
  

코드

from collections import deque

n, k = map(int, input().split())
arr = [i for i in range(1, n+1)] # 리스트 컴프리헨션
arr = deque(arr) # 리스트를 덱으로 만들어줌

result = []
while arr: # 리스트에 원소가 존재할동안
    for _ in range(k-1):
        arr.rotate(-1) # 왼쪽으로 한칸씩 돌리기
        # arr.append(arr.popleft()) # k-1번째까지는 pop
    result.append(arr.popleft()) # K번째 수를 pop해서 result에 담아준다.

print("<", end="")
for r in result:
    if r == result[-1]:
        print("{}".format(r), end="")
    else:
        print("{}, ".format(r), end="")
print(">")