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

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	256 MB	84593	41859	29519	48.448%

문제

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

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)

출력

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

예제 입력 1

7 3

예제 출력 1

<3, 6, 2, 7, 5, 1, 4>

풀이

from collections import deque

n, k = map(int, input().split())  # N은 총 사람 수, K번째 사람 제거
q = deque()
for i in range(1, n + 1):
    q.append(i)
ans = []
for i in range(n - 1):
    for j in range(k - 1):
        q.append(q.popleft())
    ans += [q.popleft()]

ans += [q[0]]
print('<' + ', '.join(map(str, ans)) + '>')

이 코드는 collections 모듈의 deque를 사용하여 요세푸스 문제를 푸는 파이썬 프로그램입니다. 요세푸스 문제는 n명의 사람이 원형으로 앉아 있고 k번째 사람을 순서대로 제거하면서 남은 사람의 순서를 구하는 문제입니다. 코드는 다음과 같은 단계를 수행합니다:

• deque라는 빈 덱(deque)을 생성하고 1부터 n까지의 정수를 오른쪽으로 추가합니다. 덱은 양쪽에서 삽입과 삭제가 가능한 리스트와 비슷한 자료 구조입니다.

• ans라는 빈 리스트를 생성하고 제거된 사람들의 번호를 저장할 예정입니다.

• n-1번 반복하면서 다음을 수행합니다:
  • k-1번 반복하면서 덱의 왼쪽에서 원소를 꺼내어 다시 오른쪽으로 추가합니다. 이렇게 하면 k번째 원소가 왼쪽에 위치하게 됩니다.
  • 덱의 왼쪽에서 원소를 꺼내어 ans에 추가합니다. 이렇게 하면 k번째 사람이 제거됩니다.

• 마지막으로 남은 한 명의 번호도 ans에 추가합니다.

• ans에 저장된 순서대로 번호들을 출력합니다.

Uploaded by N2T