[BOJ] 1158. 요세푸스 문제

Python3

문제

입출력

입출력 예시

키워드

• 구현
• 큐

주요 포인트

left는 남아 있는 사람들의 배열이다. 1부터 n까지 숫자를 리스트 안에 넣는다.
ans는 나오는 사람, 즉 요세푸스 순열(답)이 된다.

for문
cnt는 left의 인덱스이다.

5명이 있다고 할 때 k=3 이라면, [1,2,3,4,5] 에서 결과는 <3,1,5,2,4> 가 될 것이다.

1) cnt = 0
2) cnt = 2 -> ans : [3]
3) cnt = 4 -> cnt = cnt % len(left) = 0 ans : [3,1] // 3을 제외하고 [1,2,4,5] 에서 cnt[0] = 1
4) cnt = 2 -> ans : [3,1,5] // 1을 제외하고 [2,4,5] 에서 cnt[2] = 5
5) cnt = 4 -> cnt = cnt % len(left) = 0 ans : [3,1,5,2] // 5를 제외하고 [2,4] 에서 cnt[0] = 2
6) cnt = 2 -> cnt = cnt % len(left) = 0 ans : [3,1,5,2,4] // 2를 제외하고 [4] 에서 cnt[0] = 4

최종 출력
<3, 6, 2, 7, 5, 1, 4> 이러한 모양을 만들어야 한다.
'<', ','.join(ans), '>'로 맞춰준다. join으로 리스트를 합쳐준다.
이때 숫자를 문자열로 만들어서 출력한다. 그러지 않으면 TypeError가 뜸.
sep=''을 통해 공백을 없애준다. 없으면 < 3, 6, 2, 7, 5, 1, 4 > 출력된다.

최종 코드

n, k = map(int, input().split())

left = [i for i in range(1, n+1)]
ans = []
cnt = 0

for i in range(n):
    cnt += k-1
    if cnt >= len(left):
        cnt = cnt % len(left)
    ans.append(str(left.pop(cnt)))
    
print("<", ", ".join(ans), ">", sep='')

피드백

원래는 pop을 사용해서 시도해보려고 했는데 잘 되지 않았다. cnt 변수를 추가해서 k-1만큼 누적해서 더하고, cnt와 left 배열의 길이를 나눈 나머지값이 가리키는 인덱스를 최종 리스트에 추가하면 되는 문제였다.
또 출력 패턴과 sep에 대해 배울 수 있는 문제였다.