[백준] 1158_요세푸스 문제 (python)

문제

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

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

• 테스트 케이스:

#입력
7 3

#출력
<3, 6, 2, 7, 5, 1, 4>

나의 풀이

1. 오류는 안나는데, 틀림..ㅠ -> end = '' 로 하니까 맞았다!

n, k = map(int, input().split())
people = list(range(1, n + 1)) #둥글게 모여앉은 사람들
start = 0 #시작 지점 가정

print('<', end = '')
for i in range(n, 0, -1): #n부터~ n-1씩 내려가도록
    next = (start + k) % (i) - 1 #k번째 사람
    
    if next < 0:
        start = next + 1
    else:
        start = next
        
    #k번쨰 사람 제거
    if i == 1:
        print(people.pop(next), end = '')
    else:
        print(people.pop(next), ',', sep = '', end = ' ')
        
print('>')

2. 다른 사람 풀이 보고 따라하기1

n, k = map(int, input().split())
people = list(range(1, n + 1)) #둥글게 모여앉은 사람들
k_index = 0
result = []

for i in range(n): #n번만 반복하면 되니까
	k_index = (k_index + k - 1) % len(people)
	result.append(people.pop(k_index))
    
print('<' + str(result)[1:-1] + '>')

다른 사람 풀이

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='')

• 출처: https://infinitt.tistory.com/213

2. 나름 숏코딩?

n, k = map(int,input().split())
l = [*range(1, n + 1)]
p = []
i = 0

while l:
 i = (i + k - 1) % len(l)
 p.append(l.pop(i))
 
print('<' + str(p)[1:-1] + '>')

3. 숏코딩 1등

n,k = map(int, input().split())
c, *a = range(n + 1)
print(f'<{str([a.pop(c := (c + k - 1) % b) for b in a[::-1]])[1:-1]}>')

: 근데 이거.. 막상 돌리면 에러난다..?
Python Tutor에선 이렇게 에러나고
SyntaxError: invalid syntax (<fstring>, line 1)
백준에서는 맞았다고 뜬다
뭐지..