#262 백준 파이썬 [1158] 조세퍼스 문제

https://www.acmicpc.net/problem/1158

 

Solution

1부터 N까지의 순열 josephus를 만든 뒤, 리스트를 도는 temp를 만든다. 맞는 숫자를 pop하여 result리스트에 넣는 방법을 통해 풀이할 수 있다.

이때 temp에 지속적으로 K-1을 더해줌으로써(1은 pop하면서 빠지기 때문) 다음 리스트를 찾는다.

위치가 리스트를 초과하면 리스트 길이로 나누어준 나머지를 pop해준다.

 

Python Code

#입력
N, K = map(int, input().split())
josephus = [i for i in range(1, N + 1)]
result = []
temp = K - 1


for i in range(N):
    if len(josephus) > temp: #위치가 리스트를 넘지 않은 경우
        result.append(josephus.pop(temp)) #답 추가
        temp += K - 1 #다음 위치로 이동
        
    elif len(josephus) <= temp: #위치가 리스트를 넘은 경우
        temp = temp % len(josephus)
        result.append(josephus.pop(temp))
        temp += K - 1

#출력
print("<", end='')
for i in result:
    if i == result[-1]:
        print(i, end = '')
    else:
        print("%s, " %(i), end='')
print(">")