728x90
문제
요세푸스 문제는 다음과 같다.
1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다.
이제 순서대로 K번째 사람을 제거한다.
한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다.
이 과정은 N명의 사람이 모두 제거될 때까지 계속된다.
원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다.
예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.
N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.
https://www.acmicpc.net/problem/1158
입력
첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000)
출력
예제와 같이 요세푸스 순열을 출력한다.
예제
# input
7 3
# output
<3, 6, 2, 7, 5, 1, 4>문제 풀이
from collections import deque
# 입력 받기
N, K = map(int, input().split())
# N명 리스트 생성 후 deque로 변환
deq = deque([i for i in range(1,N+1)])
# 정답 변수 초기화
answer = []
while len(deq) > 0:
# pop할 K 전까지 deq의 뒤로 추가
for i in range(K-1):
deq.append(deq.popleft())
# K번째 요소를 deq에서 제거하고 answer에 추가
answer.append(deq.popleft())
print('<' + ', '.join(map(str, answer)) + '>')# 입력 받기
N, K = map(int, input().split())
# N명 리스트 생성
L = [i for i in range(1, N+1)]
# 정답 변수 초기화
answer = []
# 인덱스 변수 초기화
idx = 0
for i in range(N):
# K번째 사람 찾기
idx += K-1
# 인덱스가 L을 넘어갈 경우 원형 리스트처럼 순환
if idx >= len(L):
idx %= len(L)
# 현재 인덱스 제거하고 answer에 추가
answer.append(L.pop(idx))
print('<' + ', '.join(map(str, answer)) + '>')파이썬을 독학하시는 분들에게 도움이 되길 바라며,
혹 더 좋은 방법이 있거나 오류가 있다면 편하게 말씀 부탁드립니다.
728x90
