[백준/자료구조/큐] - 요세푸스 문제

문제

 

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

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>

 

나의 생각

 

우선 문제에서 제시한 규칙을 제대로 이해하기 위해 문제에서 제시해준대로 풀이를 진행해 보았습니다.

문제에서는 N개의 원소를 제시해 주었고, K번째 원소를 반복해서 제거해나가는 방식대로 문제를 풀도록 하였습니다.

 

즉 [1, 2, 3, 4, 5, 6, 7] 에서 3번째 원소를 반복해서 제거해 나가는 방식으로 진행하면 됩니다.

 

문제의 규칙에 따라 진행을 해보면 다음과 같습니다.

 

[1, 2, 3, 4, 5, 6, 7] -> [3, 4, 5, 6, 7, 1, 2] -> [4, 5, 6, 7, 1, 2] -> [6, 7, 1, 2, 4, 5] -> [7, 1, 2, 4, 5] -> [2, 4, 5, 7, 1] -> [4, 5, 7, 1] -> [7, 1, 4, 5] -> [1, 4, 5] -> [5, 1, 4] -> [1, 4] -> [4] -> [ ]

 

빠져나간 순서를 정리해보면

[  ]  -> [3] -> [3, 6] -> [3, 6, 2] -> [3, 6, 2, 7] -> [3, 6, 2, 7, 5] -> [3, 6, 2, 7, 5, 1] -> [3, 6, 2, 7, 5, 1, 4]

 

이 문제는 큐를 이용한 문제입니다.

 

N명의 사람들이 있고, K를 주기로 사람을 제거하며, 주기가 사람의 인원수를 초과하면 사람의 인원수로 나눈 나머지로 값을 초기화해주면 되는 문제입니다.

 

N,K = map(int,input().split())
arr = [i for i in range(1,N+1)]    # 맨 처음에 원에 앉아있는 사람들

answer = []   # 제거된 사람들을 넣을 배열
num = 0  # 제거될 사람의 인덱스 번호

for t in range(N):
    num += K-1  
    if num >= len(arr):   # 한바퀴를 돌고 그다음으로 돌아올때를 대비해 값을 나머지로 바꿈  
        num = num%len(arr)
 
    answer.append(str(arr.pop(num)))
print("<",", ".join(answer)[:],">", sep='')