BOJ #9345 디지털 비디오 디스크(DVDs)

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

BOJ #9345 디지털 비디오 디스크(DVDs)

문제 풀이

세그먼트 트리 비재귀 구현 포스팅을 작성하게 만든 문제다. Python은 어림도 없고 pypy3에서도 비재귀 방식으로 세그먼트 트리를 작성해야 했다. 풀이에는 최대-최소 알고리즘을 썼는데 생각해보니 그냥 최대 세그먼트 트리와 최소 세그먼트 트리를 분리해 구현하는게 메모리 측면에서는 손해겠지만 시간 측면에서는 손해가 아닐 수도 있겠다는 생각이 들었다.

기본 원리는 선반에 DVD가 좌표값대로 들어있음에 착안하여 left부터 right까지의 DVD를 선택했을 때 left부터 right까지의 DVD가 존재해야 하므로 최솟값이 left이고 최댓값이 right이면 해당 범위의 DVD가 모두 존재함을 보장할 수 있겠다.

• 비재귀 방식으로 0 ~ N -1 배열에 대한 세그먼트 트리 생성
• 교체 시 교체된 ㄱ밧으로 최댓/최솟값 업데이트
• 조회 시 최솟값에 left, 최댓값에 right가 매칭되면"YES" 출력, 그렇지 않으면 "NO" 출력

python 코드

import sys
input = sys.stdin.readline

def solve():
    def max_init():
        for i in range(N - 1, 0, -1):
            tree[i] = max(tree[i << 1], tree[i << 1 | 1])

    def min_init():
        for i in range(N - 1, 0, -1):
            tree[i] = min(tree[i << 1], tree[i < 1 | 1])

    def max_query(l, r):
        sol = 0
        l += N
        r += N
        while l < r:
            if l % 2 == 1:
                sol = max(tree[l], sol)
                l += 1
            if r % 2 == 1:
                sol = max(tree[r - 1], sol)
            l //= 2
            r //= 2
        return sol

    def min_query(l, r):
        sol = 0
        l += N
        r += N
        while l < r:
            if l % 2 == 1:
                sol = min(tree[l], sol)
                l += 1
            if r % 2 == 1:
                sol = min(tree[r - 1], sol)
                r -= 1
            l //= 2
            r //= 2
        return sol

    def max_update(i, val):
        tree[N + i] = val
        i += N
        while i > 1:
            tree[i >> 1] = max(tree[i], tree[i ^ 1])

    def min_update(i, val):
        tree[N + i] = val
        i += N
        while i > 1:
            tree[i >> 1] = min(tree[i], tree[i ^ 1])

    for _ in range(int(input())):
        N, K = map(int, input().split())
        INF = float('inf')
        min_tree = [INF] * (2 * N)
        max_tree = [-INF] * (2 * N)
        nums = [0] * N
        for i in range(N):
            max_tree[N + i] = i
            min_tree[N + i] = i
            nums = [i]
        for _ in range(K):
            q, a, b = map(int, input().split())
            if q:
                min_v = min_query(a, b + 1)
                max_v = max_query(a, b + 1)
                if min_v == a and max_v == b:
                    print("YES")
                else:
                    print("NO")
            else:
                nums[a], nums[b] = nums[b], nums[a]
                max_update(a, nums[a])
                min_update(a, nums[a])
                max_update(b, nums[b])
                min_update(b, nums[b])
solve()