백준 9345 : 디지털 비디오 디스크 (Python)

본문 링크

import sys,math
input=sys.stdin.readline

def init(node , start , end):

    if start==end:
        tree[node]=(L[start],L[start])
        return

    init( node*2 , start , (start+end)//2)
    init( node*2+1 , (start+end)//2+1 , end)

    tree[node]=(tree[node*2][0] , tree[node*2+1][1] ) #트리의 값은 왼쪽자식의 최소값과 오른쪽자식의 최대값을 가진다.

def update(node , start , end ,index , value):

    if index<start or index>end:
        return

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

    update(node*2 , start , (start+end)//2 , index,value)
    update(node*2+1 , (start+end)//2+1 , end , index , value)

    tree[node]=(min(tree[node*2][0] , tree[node*2+1][0]) , max(tree[node*2][1] , tree[node*2+1][1] ))
    # 트리는 왼쪽자식에서 최소값과 오른쪽자식에서 최대값을 저장한다.

def query(node, start , end , left , right):

    if left>end or right<start:
        return True

    if left<=start and right>=end:  # 범위를 포함하고 있다면

        if left<=tree[node][0] and right>=tree[node][1]:
            # 트리의 값이 최소값보다 크고 최대값보다 작다면.
            # 즉 트리의 값이 범위 내에 있다면 True를 반환한다.
            # 왜냐하면 최대값과 최소값이 존재한다는 의미이므로 디스크가 전부 존재한다는 의미이기 때문이다.
            return True
        else:
            return False

    return query(node*2 , start , (start+end)//2 , left , right ) and query(node*2+1 , (start+end)//2+1 , end , left,right)



for i in range(int(input())):

    N,K=map(int,input().split())

    L=[ _ for _ in range(N+1)]

    height=math.ceil(math.log2(N))
    tree_size=1<<(height+1)
    tree=[ (-1,-1) ] *(tree_size+1) #초기값은 -1로 설정한다.

    init(1,1,N)
    for j in range(K):

        Q,A,B=map(int,input().split())

        A+=1 ; B+=1 # 1번부터 시작한다.

        if Q==0:
            update(1 , 1, N , A , L[B] ) # A 에다가 리스트 B 의 값을 넣는다.
            update(1, 1, N , B, L[A] ) # B 에다가 리스트 A의 값을 넣는다.
            L[A], L[B] = L[B], L[A]
        else:

            if query(1,1,N,A,B):
                print("YES")
            else:
                print("NO")

📌 어떻게 접근할 것인가?

두가지 쿼리가 주어집니다.

• $A$ 와 $B$ 번의 값을 바꾼다.

• $A$ 부터 $B$ 번까지 범위에서 $DVD$ 가 $A$부터 $B$까지 모두 포함하는가?

세그먼트 트리를 사용했습니다.

먼저 tree 를 2차원 배열로 구성해줍니다.

tree=[ (-1,-1) ] *(tree_size+1) #초기값은 -1로 설정한다.

tree 에서 우리가 저장할 값은 최대값과 최소값 입니다.

$A$ 번 부터 $B$ 번까지 존재하는지 판별할때 $A$ 번부터 $B$ 번을 모두 판별하면 시간초과가 납니다.
따라서 $A$번부터 $B$ 번까지 $DVD$ 가 존재할때 그 범위내의 최대값과 최소값 을 세그먼트 트리에 저장 한 후에

특정 범위에 $DVD$ 가 존재하는지 판별하는 것은 그 범위내의 최대값과 최소값이 존재하는지 판별하면 됩니다.

예를들면 $3$ 번 부터 $7$ 번까지 $DVD$ 가 존재하는지 판별하기 위해서는 세그먼트 트리에 저장한 범위를 탐색하여서 최소값이 $3$ 보다 작고 최대값이 $7$ 보다 크다면 범위를 포함하므로 $3$ 번 부터 $7$ 번의 $DVD$ 가 모두 존재한다는 것을 뜻합니다.

처음 트리에서 초기값을 설정하는 함수는 init 함수입니다.

tree[node]=(tree[node*2][0] , tree[node*2+1][1] ) 
#트리의 값은 왼쪽자식의 최소값과 오른쪽자식의 최대값을 가진다.

이때 중요한 부분은 위 코드인데 , 트리의 초기값을 설정할때 2차원 배열로 설정했습니다.
왼쪽값에서는 왼쪽자식의 최대값 , 오른쪽값은 오른쪽 자식의 최대값을 담습니다.

즉 왼쪽자식은 최소값을 , 오른쪽자식은 최대값을 갱신해줍니다.

그다음으로 update 함수입니다.

tree[node]=(min(tree[node*2][0] , tree[node*2+1][0]) , max(tree[node*2][1] , tree[node*2+1][1] ))

이때 중요한 부분은 위 코드와 같습니다.

왼쪽 부모는에는 최소값을 저장해야 하므로 자식의 왼쪽값 2개중에 더 작은 값을 가지고
오른쪽 부모는 최대값을 저장해야 하므로 자식의 오른쪽값 2개중 더 큰 값을 가져야 합니다.

다음으로 쿼리 query 함수입니다. 이는 DVD 가 존재하는지 판별합니다.

def query(node, start , end , left , right):

    if left>end or right<start:
        return True

    if left<=start and right>=end:  # 범위를 포함하고 있다면

        if left<=tree[node][0] and right>=tree[node][1]:
            # 트리의 값이 최소값보다 크고 최대값보다 작다면.
            # 즉 트리의 값이 범위 내에 있다면 True를 반환한다.
            # 왜냐하면 최대값과 최소값이 존재한다는 의미이므로 디스크가 전부 존재한다는 의미이기 때문이다.
            return True
        else:
            return False

    return query(node*2 , start , (start+end)//2 , left , right ) and query(node*2+1 , (start+end)//2+1 , end , left,right)

여기 부분은 전부 중요합니다.

if left>end or right<start:
	return True

왼쪽의 값이 최대값보다 크거나 오른쪽값이 최소값보다 작다는 것은 범위를 벗어난다는 뜻이므로 True 를 반환합니다.

if left<=start and right>=end:  # 범위를 포함하고 있다면
        if left<=tree[node][0] and right>=tree[node][1]:
            # 트리의 값이 최소값보다 크고 최대값보다 작다면.
            # 즉 트리의 값이 범위 내에 있다면 True를 반환한다.
            # 왜냐하면 최대값과 최소값이 존재한다는 의미이므로 디스크가 전부 존재한다는 의미이기 때문이다.
            return True
        else:
            return False

중요한 것은 이부분 입니다. 범위를 포함하고 있을때 , 트리의 최소값이 왼쪽값보다 크고 트리의 최대값이 오른쪽값보다 작다면 포함한다는 의미이므로 True 를 반환합니다. 그렇지 않을 경우 False 를반환합니다.

예를 들어 $3$ 에서 $7$ 이라는 범위가 있을때

$left$ 는 $3$ 이고 $right$ 는 $7$ 이됩니다.

이때 $tree[node][0]$ 의 값 , 즉 트리의 최소값이 $left$ 보다 크다면 ,
그리고 $tree[node][1]$ 의 값 , 즉 트리의 최대값이 $right$ 보다 작다면

• $left = 3$ , $right = 7$
• $tree[node][0] = 5$ , $tree[node][1] = 6$

위와 같이 설정해보겠습니다.
이때 $5$~$6$ 의 범위는 $3$~$7$ 범위에 포함되므로 $DVD$ 가 $5$~$6$ 범위일때 전부다 존재한다고 말 할 수 있습니다.

return query(node*2 , start , (start+end)//2 , left , right ) and query(node*2+1 , (start+end)//2+1 , end , left,right)

또한 return 을 사용할때 두번을 동시에 하는데 이때 and 를 사용해야합니다.
중요한것은 한번이라도 False 값이 존재하는지 체크 하는것입니다.

만약 False and True 는 반환시 False 를 해줍니다.

즉 True and True 에서만 반환을 True 를 해주고 , False and True , True and False , False and False 에서는 False 를 반환하기 때문에

and 를 사용하여서 한번이라도 False 값이 존재하는지 체크합니다.

이제 쿼리 실행에 대해 알아봅시다.

if Q==0:
	update(1 , 1, N , A , L[B] ) # A 에다가 리스트 B 의 값을 넣는다.
	update(1, 1, N , B, L[A] ) # B 에다가 리스트 A의 값을 넣는다.
	L[A], L[B] = L[B], L[A]

총 2번을 해줘야 합니다. 서로 값을 바꾸는 것이기 때문입니다.
이후 리스트의 값도 서로 바꿔줍니다.

if query(1,1,N,A,B):
	print("YES")
else:
	print("NO")

쿼리 함수 실행시 False 가 하나라도 존재한다면 NO 를 출력합니다.
모두 True 일 경우 YES 를 출력합니다.

노드의 시작번호는 1번부터 하였습니다.

pypy 로 제출해야하며 시간초과가 날 수 있으므로 최대한 불필요한 연산은 지워야 합니다.

세그먼트 트리를 2차원 배열로 활용하여서 최대값과 최소값을 저장하고 그것을 쿼리에 맞게 활용할 수 있습니다.