[Python] 백준 9345번: 디지털 비디오 디스크(DVDs)

https://www.acmicpc.net/problem/9345

9345번: 디지털 비디오 디스크(DVDs)

 

import sys
import math
input = sys.stdin.readline


def getTreeLength():
    # 2의 제곱꼴인지 확인
    if N & (N - 1) == 0:
        return 2*N - 1
    else:
        return pow(2, math.ceil(math.log(N, 2)) + 1) - 1


def initializeSegmentTree(index, start, end):
    if start == end:
        tree[index] = (nums[start], nums[start])
        return

    mid = (start + end)//2
    initializeSegmentTree(index*2, start, mid)
    initializeSegmentTree(index*2+1, mid+1, end)
    tree[index] = (tree[index*2][0], tree[index*2+1][1])


def modifySegmentTree(index, target, value, start, end):
    if target < start or end < target:
        return

    if start == end:
        tree[index] = (value, value)
        return

    mid = (start + end)//2
    modifySegmentTree(index*2, target, value, start, mid)
    modifySegmentTree(index*2+1, target, value, mid+1, end)
    tree[index] = (min(tree[index*2][0], tree[index*2+1][0]),
                   max(tree[index*2][1], tree[index*2+1][1]))


def queryInSegmentTree(index, range, start, end):
    if range[1] < start or end < range[0]:
        return True

    if range[0] <= start and end <= range[1]:
        return range[0] <= tree[index][0] and tree[index][1] <= range[1]

    mid = (start+end)//2
    return queryInSegmentTree(index*2, range, start, mid) and queryInSegmentTree(index*2+1, range, mid+1, end)


if __name__ == '__main__':
    T = int(input())

    for _ in range(T):
        N, K = map(int, input().split())

        nums = [i for i in range(N+1)]

        tree = [(-1, -1)]*(getTreeLength())
        initializeSegmentTree(1, 1, N)

        for _ in range(K):
            q, a, b = map(int, input().split())
            a += 1
            b += 1

            if q == 0:
                # xchg
                modifySegmentTree(1, a, nums[b], 1, N)
                tmpA = nums[a]
                nums[a] = nums[b]
                modifySegmentTree(1, b, tmpA, 1, N)
                nums[b] = tmpA
            else:
                # query
                if queryInSegmentTree(1, (a, b), 1, N):
                    print("YES")
                else:
                    print("NO")

 

https://rccode.tistory.com/entry/Python-%EB%B0%B1%EC%A4%80-2357%EB%B2%88-%EC%B5%9C%EC%86%9F%EA%B0%92%EA%B3%BC-%EC%B5%9C%EB%8C%93%EA%B0%92

[Python] 백준 2357번: 최솟값과 최댓값

위 게시글에서의 (최솟값, 최댓값)을 저장하는 세그먼트 트리에서 조금 더 변형된 문제이다.

 

우선 이 문제를 최소최대 세그먼트 트리로 푼다는 접근은 i번 선반에 i번 DVD가 있다는 것으로부터 시작된다. 정상적인 상태일 때, n~m 선반에는 (n, n+1, n+2, ..., m-1, m) DVD가 있을 것이다. 이 때의 최소, 최댓값은 n, m이고 말이다. 그럼 여기서 n+1 선반의 것이 k DVD와 바뀌었다고 해보자. 그렇다면 선반에는 (n, k, n+2, ..., m-1, m)가 있게 된다. 여기서 경우의 수가 나뉘어진다.

먼저 k < n일 경우에는, 해당 범위의 최소, 최댓값에서 최소값이 변동된다.

다음으로 n <= k <= m일 경우에는 그 안에서 바뀐 것이므로 문제될 것이 없다.

마지막으로, m < k일 경우에는, 최댓값이 변동하게 된다.

 

우리는 이것을 이용하여 이 문제를 해결하면 된다.

먼저 최솟값과 최댓값을 저장하는 세그먼트 트리를 initializeSegmentTree()를 통해 구성한다. 이 때 최적화된 부분이 있다.

tree[index] = (tree[index*2][0], tree[index*2+1][1])

원래였으면, tree[index*2][0]과 tree[index*2+1][0] 중에 더 작은 값을, tree[index*2][1]과 tree[index*2+1][1] 중에 더 큰 값을 넣었을 텐데, 이 문제에서는 초기에 DVD가 정렬되어 있으므로 이렇게 할 수 있다.

 

다음으로 modifySegmentTree()인데, 이부분은 딱히 변형된 것이 없다.

 

마지막으로 queryInSegmentTree() 함수이다. 이 함수는 해당 범위에서의 최솟값, 최댓값을 얻어오는 함수였고, 이것을 호출한 뒤에 리턴값이 (a, b)와 같은지를 비교하는 식으로 문제를 풀었었는데, 이것이 최적화되어 현재의 코드로 나타나게 된 것이다. 새로 설계된 이 함수는, 트리의 a~b 범위를 탐색하면서, 트리의 값(최솟값, 최댓값)이 한번이라도 a~b라는 범위를 벗어났는지를 검사하는 목적을 두고 있다.

함수의 앞부분에는 start, end가 범위를 벗어났는지를 체킹하고 True를 반환해주는데, 함수의 설계를 보면 당연하다.

다음으로 start, end가 모두 범위 내에 있을 때, 현재 트리의 값이 정상적인지(즉, a~b 내에 있는지)를 체킹하여 리턴해준다. 여기서 False가 나오게 되면(한번이라도 범위를 벗어나면) 이 재귀함수는 결과적으로 False를 리턴하게 된다.

마지막으로 재귀 함수 2개를 and 연산으로 묶어서 리턴해준다. 이렇게 하면 원하는 재귀함수를 설계할 수 있다.

요약하자면, 검색 범위 내에 있는 모든 트리의 값들 중에, 하나라도 range를 벗어나는 것이 있다면 False를 반환하게 된다.

 

이 3개의 함수를 이 문제의 입출력에 따라 적절히 넣어준다. 다만 q==0인 경우, DVD 1개를 바꾸는 것이 아니라, DVD 2개를 서로 exchange하는 것이므로 modifySegmentTree()를 2번 호출해준다.