[Python] BOJ 1158 : 요세푸스 문제

요구사항 

• 시간 제한 2초, N의 크기도 작아 넉넉하다. 메모리 제한 또한 마찬가지
• N, K 가 주어질 때 요세푸스 순열을 구하는 프로그램을 출력하라. 

설계

• [1, 2, 3, 4, 5, 6, 7] 사람이 앉아 있다고 했을 때,
• 1, 2번 사람을 7번 뒤로 넣는다. [3, 4, 5, 6, 7, 1, 2]  []
• 3번사람을 뺄 수 있다. [4, 5, 6, 7, 1, 2]  [3]
• 4번, 5번 사람을 2번 사람 뒤에 넣는다. [6, 7, 1, 2, 4, 5]  [3]
• 6번 사람을 뺄 수 있다.  [7, 1, 2, 4, 5]  [3, 6]

위와 같이 Queue의 성질을 이용해서 문제를 풀 수 있다. 

추가로  순열을 출력할 때, replace함수와 join함수 중 시간 복잡도가 낮은 걸 택하고 싶어 고민했었다. 

join 함수는 리스트의 모든 문자열을 하나의 문자열로 결합하기 때문에 O(N)을 갖는다.

join은 반복 가능한(이터럴) 객체의 요소를 하나의 문자열로 결합하는 데 사용된다. 따라서 리스트에 숫자나 다른 자료형이 있으면 오류가 발생한다. 만약 출력하고 싶다면. 아래와 같이 하면 된다. 

num_list = [3, 4, 5]
print(', '.join(map(str, num_list))

 

replace 함수는 .replace(old, new) old 문자열을 찾아서 new 문자열로 바꾸기 때문에, O(n * m) 의 복잡도를 갖는다.

여기서 n은 원복 문자열의 길이 m은 교체할 패턴의 길이이다. 

구현

from collections import deque

N, K = map(int, input().split())
queue = deque(range(1, N + 1))
result = []

while queue:
    for _ in range(K-1):
        queue.append(queue.popleft())
    result.append(queue.popleft())

print("<" + ", ".join(map(str, result)) + ">")