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

11866번: 요세푸스 문제 0

• 백준(boj) 11866번

문제

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

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)

출력 조건

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

»input

7 3

»output

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

첫번째 시도 .

 n,k=map(int,input().split())
 
 #num 배열에 사람들을 담음.
 num = list(range(1,n+1))
 index = 0
 result = []
 
 #k번째 사람을 제거하기위해선, 배열의 인덱스는 -1씩 작음으로
 #인덱스 k-1번째 사람을 제거 해주어야함.
 #그리고 사람이 한명 사라지면 배열의 크기가 줄어들기 때문에 그 다음 제거해야할 사람 또한
 #(k-1)x2 번째 인덱스의 사람을 제거해야함.
 for _ in range(n):
     index+=k-1
 
 #인덱스가 남아있는 수열의 길이 보다 같거나 크다면 len(num)=index일때는 사실상 인덱스가 길이를 넘어섬.
 #그래서 같거나 크다라고 해주어야함.
 #넘어선 길이만큼을 다시 앞에서 부터 제거해주어야함.
     if len(num) <= index:
         index=index%len(num)
         
     result.append(num.pop(index))
 result=map(str,result)
 
 print("<",", ".join(result),">",sep="")

🌝 Thinking

지금까지의 코드가 나오기 위해서 사실 고민을 엄청 많이 했다. 사람이 원형으로 앉아 있으니,

리스트를 길게 이어 붙여서 원을 만들어야하나 ? 이래 저래 생각을 많이 했는데,

생각이 많아져서 오히려 문제푸는데 독이 되었던 것 같다. 사람들이 원형으로 앉아 있는 효과를 내기위해

넘어서는 만큼의 index를 앞에서의 재출발하는 index로 사용하는게 핵심 포인트였던 것 같다.

리스트의 인덱스는 번째수보다 -1작다.(인덱스는 0부터 시작하기 때문)

이게 생각보다 머릿속을 많이 혼잡하게 했던 것 같다.

success

💡 깨달은 점.

1. 배열의 인덱스와 관련된 문제는 항상 머릿속을 차분히 한 후 천천히 머릿속 컴파일러를 잘 돌려야하는 듯 하다.