[Python] 백준 1158번 - 요세푸스 문제

 

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)

 

출력

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

*수정 전 코드

from collections import deque
n, k = map(int, input().split())
data = deque(range(1, n + 1))
yose = []
str_yose = []

for _ in range(1, n + 1):
    data.rotate(-k + 1)
    yose.append(data.popleft())

for i in range(n):
    str_yose.append(str(yose[i]))

print('<' + ', '.join(str_yose) + '>')

요세푸스 문제는 N명의 사람이 모두 제거될 때까지 K번째 사람을 제거합니다. 저는 rotate를 사용하면 된다는 힌트를 얻고 1부터 N까지 입력된 덱에서 K번째 인덱스를 맨 앞으로 빼준 뒤, popleft()를 사용하여 순서대로 리스트에 저장하고 출력을 위해 string형태의 리스트에 따로 저장하여 출력했습니다.

 

근데, 블로그를 쓰면서 다시 보니까 굳이 string으로 바꾸는 작업을 위해서 for문을 하나 더 써야하나? 라는 생각이 들어서 아래와 같이 고쳐봤는데요.

 

* 수정 후 코드

from collections import deque
n, k = map(int, input().split())
data = deque(range(1, n + 1))
yose = []

for _ in range(1, n + 1):
    data.rotate(-k + 1)
    yose.append(str(data.popleft()))
    
print('<' + ', '.join(yose) + '>')

이것도 물론 잘 돌아갑니다만, 위에 있는 코드가 조금 더 빠르게 돌아가는 결과가 나왔습니다. (왜 그런지 아신다면 댓글 부탁드립니다 ㅠㅠ)

수정 전: 92ms

수정 후: 96ms

 

뭔가 궁금해서 찾아보긴 했는데 만족할만한 정보는 못찾았습니다 ㅠㅠ...

 

피드백 언제나 환영합니다. (이 글은 더요!!!)