[백준/1158/파이썬] 요세푸스 문제

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

1158번: 요세푸스 문제

조건

• 1~N번까지 , N명의 사람이 원을 이루면서 앉아 있고, 정수 K가 주어짐.
• 순서대로 K번째 사람을 제거한다.(오징어 게임?!)
• 한 사람이 제거되면, 남은 사람들로 이루어진, 원을 따라 이 과정을 계속해 나간다.
• 요세푸스 순열은 ,이 제거된 사람을 순서대로 나열한 것이다
• 1<=K<=N<=5000, K= 제거되는 대상, N= 인원

SOL

 

상황을 보자면, 원탁에서 7명이서 지금 러시안 룰렛마냥 3번째 사람이 죽어가는 상황.

3 → 6 → 2 →7 → 5 → 1 →4 순으로 간다.

1. 남은 사람 중, 3번째인 사람을 알아야함.
2. 계속 탐색을 진행해야함. (남은 사람 중 , 3번쨰인 사람을 알기위해서 + 탈락한 사람은 빼기위해

Queue를 이용해서, 1~N까지 배열에서 출발해서, 왼쪽으로 K-1칸씩 옮겨가면서 POP하면 되지않을까?

(보니하니에 돌려돌려 돌림판을 생각하면 될듯. 12시 방향에 -> 생긴 화살표있고, 그 사람이 죽는거임! 그래서, 3번째 라고하면, 왼쪽으로 2번 돌리면 되니까 , K-1, 그리고 해당 사람을 POP해서 없애주면됨!)

from collections import deque

n,k=map(int,input().split())

arr = [x for x in range(1,n+1)]

hq = deque(arr)
yose=[]
rotate= k-1
while hq:
	hq.rotate(-rotate)
	yose.append(hq.popleft())
#출력 
print("<",end="")
for i in range(len(arr)):
	print(f"{yose[i]}",end="")
print(">")
#이런느낌?
# 주의) 배열의 크기가 k보다 작아질때도 잘 작동할까? rotate라면, 해야함!