[백준 1158: 요세푸스] 파이썬 풀이

문제

요세푸스 문제는 다음과 같다.

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000)

출력

예제와 같이 요세푸스 순열을 출력한다.

 

---

✏️ 풀이

 

 

예제) 입력 7 3 일 때,

 

• 7명의 사람이므로 1부터 7까지 순서대로 [1, 2, 3, 4, 5, 6, 7] 라는 배열을 만듦
• 3번째 사람이 출력되어야 하므로 시작 지점 k-1((index)) => k-1 요소를 제거
• 그 이후 계속 k-1에서 3번째 이후 사람이 나와야 함 -> 3을 더해줌 & 하나가 제거되었으므로 한 칸씩 당겨야 함 : index 1을 빼주어야 함 => index + k -1 요소를 제거 
  • 인덱스가 리스트의 길이를 초과했을 때는, 돌아가서 앞으로 넘어가야 하기 때문에 길이를 빼줌
  • 길이를 빼주었는데도 인덱스가 초과할 경우를 대비해 while 문으로 처리해주었다 
  • ❗️ 다른 정답들을 보니까 이 부분을 나머지로 처리한 게 더 좋아보였다

---

코드

import sys
input = sys.stdin.readline

n, k = map(int, input().split()) # n명의 사람, k번째 사람을 제거

num_list = list(range(1, n+1)) # 1부터 n까지 리스트 생성
index = k-1 # 초기 인덱스 값을 k-1로 설정
result = [] # 결과를 담을 리스트 

while num_list: # num_list 요소가 빌 때까지 반복
  result.append(num_list.pop(index)) # index에 위치한 요소를 pop
  index = index + k - 1 # k 만큼 인덱스 증가, 방금 pop한게 지워지면서 인덱스가 하나 앞으로 가므로 1을 더 빼줌
  
	if len(num_list) > 0:
    	while(index >= len(num_list)):
      	index = index - len(num_list) 
		# 인덱스가 초과했을 때, 앞으로 넘어가기 위해서 길이를 빼줌 
		# 길이를 빼주었는데도 인덱스가 초과할 경우를 대비해 while문으로 처리
		# 다른 정답 보니까 이 부분을 나머지로 처리한게 더 좋아보였음 

# 출력
print('<', end="")
print(*result, sep=", ", end="")
print('>', end="")