요세푸스 문제

• 요세푸스 순열을 출력하는 문제
• 1~n까지의 수를 실제로 생성해서 k번째 수들을 하나씩 지워가면서 출력한다. Order Statistic Tree를 사용하면 지워야 할 수를 찾아서 지우는 것을 O(logn)에 처리할 수 있다. 총 시간복잡도는 O(nlogn)이 된다.
• 하지만 n의 크기제한이 작다보니 실제로는 O(n^2) 로 구현한 코드들이 더 빨리 돌아간다. 요세푸스 문제 2 문제는 이 문제와 동일하지만 n의 크기제한을 늘려서 반드시 O(nlogn) 솔루션으로만 풀리도록 바뀌었다.

"""Solution code for "BOJ 1158. 요세푸스 문제".

- Problem link: https://www.acmicpc.net/problem/1158
- Solution link: http://www.teferi.net/ps/problems/boj/1158

Tags: [OrderStatisticTree]
"""

from teflib import segmenttree


def main():
    N, K = [int(x) for x in input().split()]
    nums = segmenttree.OrderStatisticTree([1] * N)
    order = 0
    answer = []
    for _ in range(N):
        order = (order + K - 1) % nums.size()
        num = nums.kth(order + 1)
        nums.add(num, -1)
        answer.append(num + 1)

    print('<', end='')
    print(*answer, sep=', ', end='>')


if __name__ == '__main__':
    main()

• Dependency: teflib.segmenttree.OrderStatisticTree