• 사실 문제를 얼핏 보자마자, Order Statistic Tree를 써서 풀어야 하는 문제라고 생각을 했고, 파이썬에서는 세그먼트 트리 기반의 구현체를 사용해야 할것이라고 생각했다. 그리고 그렇게 풀었다.
• 그러나 제출 후에 다른 사람 코드를 보면서 대부분 링크드 리스트로 풀었다는 것을 알았고,, 다시 문제를 꼼꼼히 읽어보니 “X들의 값을 합친 결과가 1,000,000 이하인 경우만 입력으로 주어집니다.” 라는 조건이 더 있다는 것을 그제서야 알게 되었다. 공식 해설 에서도 링크드 리스트에 기반한 풀이를 정해로 소개하면서 세그먼트 트리에 기반한 방법을 별해로 소개하고 있다.
  • 공식 해설에서 소개하는 세그먼트 트리에 기반한 풀이는 사실 최적 방법이 아니다. k번째 원소를 구간합과 이분탐색을 이용해서 O(log^2(n))에 계산한다고 있다고 소개하는데, 이분탐색을 쓰지 않고 O(logn)에 계산할수 있다. 세그트리 대신 펜윅트리를 사용해도 마찬가지.
• 링크드 리스트로 풀 경우에는 그냥 시키는대로 구현하면 된다. U X 와 D X 명령도 실제로 링크를 따라 X칸 이동하는 것으로 처리하면 되고, 시간 복잡도는 O(X)가 걸린다. 커맨드들을 처리하는 총 시간 복잡도는 O(q+m) 이 된다 (q=커맨드의 갯수, m=이동 거리의 총합, q≤200,000, m≤1,000,000). 링크드 리스트를 구축하고, 출력값을 만드는 것까지 포함하면 총 O(n+q+m)이 된다. 실제 구현은 안해봤다.
• Order statistic tree를 이용해서 풀 경우는, U X 와 D X 명령은 k값을 바꾸고 k번째 행을 구하는 방식으로 처리된다. (정확히는 k값만 바꿔놓고 실제로 삭제를 할 때에 k번째 행을 구하도록 구현하고 있지만, 복잡도 계산에서는 차이는 없다.) k번째 행을 구하는 것은 O(logn)에 처리가 되고, 이것이 가장 시간이 많이 걸리는 커맨드이다. 따라서 커맨드 처리의 총 시간복잡도는 O(qlogn). 세그트리를 만들고, 결과값을 만드는 것까지 포함하면 O(n + qlogn)
• 구현할 때 실수하기 쉬운 부분은, 열을 지울때 k값이 안바뀌지만, 마지막 열을 지울때는 k값이 1 줄어들어야 한다는 것. 그리고 지운 열을 복구할때 복구한 열이 현재 위치보다 위에 있으면 k값을 1 증가시켜야 한단는 것.

"""Solution code for "Programmers 81303. 표 편집".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/81303
- Solution link: http://www.teferi.net/ps/problems/programmers/81303
"""

from teflib import segmenttree


def solution(n, k, cmd):
    table = segmenttree.OrderStatisticTree([1] * n)
    stack = []
    k += 1
    for cur_cmd in cmd:
        if cur_cmd == 'C':
            num = table.kth(k)
            table.add(num, -1)
            stack.append(num)
            k = min(k, table.size())
        elif cur_cmd == 'Z':
            num = stack.pop()            
            if num < table.kth(k):
                k += 1
            table.add(num)
        else:
            c, x = cur_cmd.split()
            k += int(x) * (1 if c =='D' else -1)

    return ''.join('O' if table.count(i) > 0 else 'X' for i in range(n))

• Dependency: teflib.segmenttree.OrderStatisticTree