[백준] 11866 요세푸스 문제 0

문제

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

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 ≤ 1,000)

출력

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

예제 입력 1

7 3

예제 출력 1

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

풀이

이 문제를 보고, 처음에는 배열을 선언한 후에, 배열에서 값을 제거해나가면서, 탐색 인덱스를 기준으로 + k 를 했을 때 배열의 마지막 인덱스보다 큰 경우, 이를 다시 앞을 탐색하도록 탐색 인덱스 값을 변경하는 로직을 생각했었다.

그러나 배열에서의 제거 + 탐색 인덱스 재설정은 생각보다 복잡했고, 배열에서 중간에 무언가를 삭제하고, 그 부분을 자동으로 채운다는게 깨름칙했다. 따라서, 큐로 풀면 원형 순회의 형태를 구현하면서도, 탐색인덱스 재설정 없이 무조건 제일 앞에 있는 값을 제거할 수 있다고 생각하여 큐를 사용하였다.

로직은 다음과 같다.
1. 원형 순회를 하면서(앞에껄 뽑아서 다시 뒤에 넣음) 탐색 횟수를 증가시키는데,
2. K번째 사람(= 탐색 횟수가 K의 배수 번째인 사람)일 경우, 뽑은 후 기록(다시 안넣음)
3. 배열이 빌때까지 1-2 과정을 반복한다.

처음 생각한 풀이(배열 사용)도 풀리긴하겠지만, 요세푸스 순열의 경우는 큐가 매우 편하다는 것을 알게 되었다.

import sys
from collections import deque
input = sys.stdin.readline

n, k = map(int, input().split())
queue = deque()
ans = []

for i in range(1, n+1):
    queue.append(i)

cnt = 1 # 번째 수 카운트 변수, 제일 처음은 1이 되어야 함(헷갈림 주의)
while queue:
    # k 번째인 경우(k의 배수인 사람을 만난 경우) -> pop 후 ans 에 저장 
    if cnt % k == 0: #
        ans.append(queue.popleft())
        cnt += 1
    else:
        v = queue.popleft()
        queue.append(v)
        cnt += 1 # 탐색 횟수 증가

print('<', end='')
for idx, val in enumerate(ans): 
    if idx == len(ans) - 1:
        print(val, end='')
    else:
        print(val, end=', ')
print('>')