[86일차][백준][자료구조, 큐][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	<3, 6, 2, 7, 5, 1, 4>

 

 

코드 및 설명

import sys

n, k = map(int, sys.stdin.readline().strip().split(" "))
n_arr = [ i for i in range(1, n+1) ]
cursor = 0
answer = []

while len(n_arr) > 0:    
  cursor += k - 1
  if cursor >= len(n_arr):
    cursor %= len(n_arr)
        
  answer.append(n_arr.pop(cursor))  
  
print('<'+', '.join(str(val) for val in answer)+'>')

 

이 문제는 요세푸스 문제, 순열이라고 한다. 예제로 한번 쉽게 설명해보겠다.

 

예제 n=7이 주어지고 k=3이 주어진다.

 

일단 7까지 쭉 나열을 해준다.

 

1 2 3 4 5 6 7

 

배열에 형태로 만들어주고 k에 값이 3이니까 3번째 있는 수(배열 0,1,2 즉 2의 자리값을 빼준다는 거다.)를

 

pop 해주고 값을 answer 저장

 

answer   = [3]

 

1 2 4 5 6 7

 

이 형태에 배열이 만들어지고 다시 반복하는 데 이때 cursor의 위치는 아까와 같이 3번째있는 수에 자리에 

 

있는 상태인데 이 자리에서부터 다시 3번째 있는 수로 이동한다. 즉 배열의 2번째 자리(배열값으로 보면 4번)에

 

cursor가 있었는 데 이동을 k -1 만큼하면 배열의 4번째자리로 이동하고 이걸 pop 해주고 값을 answer 저장

 

answer   = [3, 6]

 

1 2 4 5 7

 

cursor 위치는 4번째인데 여기서 k-1만큼 이동하면 6번째 자리이다. 하지만 지금 배열에 크기가 5이기때문에 cursor값이 

 

배열 크기보다 커졌기 때문에 여기서 체크를 해줘야한다. cursor %= len(n_arr) 해주면 6 % 5 이기때문에

 

1(배열의 자리수)이 나온다.

 

answer = [3, 6, 2]

 

1 4 5 7

 

반복 해주면

 

1 4 5

 

answer = [ 3, 6, 2, 7 ]

 

1 4

 

answer = [ 3, 6, 2, 7, 5 ]

 

4 

 

answer = [ 3, 6, 2, 7, 5, 1 ]

 

최종 --> answer = [ 3, 6, 2, 7, 5, 1, 4 ]

 

여기서 한 가지 출력 형태를 봐야한다. 처음에 그냥 제출 했다가... 틀렸습니다가 떴다 ㅎㅎ

 

배열 형태가 아닌 <3, 6, 2, 7, 5, 1, 4> 이렇게 해줘야하기 때문에 print문에서 꼭 바꿔주고 출력해야한다. 

 

출력 방법이야 뭐 다양하니... 잘 알아서?ㅎㅎㅎ