사용자 도구

사이트 도구


ps:problems:boj:1168

요세푸스 문제 2

ps
링크acmicpc.net/…
출처BOJ
문제 번호1168
문제명요세푸스 문제 2
레벨플래티넘 4
분류

Order statistic tree

시간복잡도O(nlogn)
인풋사이즈n<=100,000
사용한 언어Python
제출기록42960KB / 568ms
최고기록568ms
해결날짜2021/08/07

풀이

  • 요세푸스 문제 에서 n의 크기 제한을 늘린 문제. 요세푸스 문제은 O(n^2) 솔루션으로도 통과 가능했지만, 이 문제는 O(nlogn) 으로 풀어야 한다. 풀이는 요세푸스 문제 참고.
  • 하지만 이 문제는 n의 크기제한이 늘어난 것 외에도, 제한시간이 언어별로 따로 정해져있고, python기준으로 상당히 타이트하다. python과 pypy이 동일하게 750ms의 제한시간을 갖고 있는데, 요세푸스 문제 의 O(nlogn) 코드를 그대로 복붙해서 제출할 경우 python은 시간초과, pypy는 약 250ms정도에 통과된다.
  • Python에서 통과시키기 위해서는 동일한 알고리즘에서 열심히 상수 최적화를 하는 과정이 필요했다.teflib.segmenttree.OrderStatisticTree를 사용해서 kth와 add함수를 호출하던 방법 대신에, k번째 수를 찾으면서 바로 delete 시키는 함수를 새로 만들었고, 클래스를 사용하는 대신 그냥 메인함수 안에 로직을 옮겨오는 방식으로 쥐어짜서 최적화를 하고서야 python3으로도 통과시킬수 있었다.

코드

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

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


def main():
    def delete_kth(k: int):
        i = 1
        while i < tree_size:
            i += i
            t = tree[i]
            if t < k:
                k -= t
                i += 1
            tree[i] -= 1
        tree[1] -= 1
        return i - tree_size

    N, K = [int(x) for x in input().split()]

    tree_size = 1 << (N - 1).bit_length()
    tree = [0] * (tree_size + tree_size)
    tree[tree_size:tree_size + N] = [1] * N
    for i in range(tree_size - 1, 0, -1):
        tree[i] = tree[i + i] + tree[i + i + 1]
        
    order = 0
    answer = []
    for i in range(N, 0, -1):
        order = (order + K - 1) % i
        num = delete_kth(order + 1)
        answer.append(num + 1)

    print('<', end='')
    print(', '.join(str(x) for x in answer), end='>')


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
X E T X N
 
ps/problems/boj/1168.txt · 마지막으로 수정됨: 2021/08/07 15:30 저자 teferi