[Python3] 9345 디지털 비디오 디스크(DVDs) - 플래티넘 3

• 2022.02.22 포스팅 기준 solved.ac 문제 등급 : 플래티넘 3
• 단계별로 풀어보기 -> 세그먼트 트리
• 알고리즘 분류
  • 자료구조
  • 세그먼트 트리

 

<링크>
https://www.acmicpc.net/problem/9345

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

시간제한	메모리제한
2 초	256 MB

 

---

<문제>
최근 유튜브와 같은 온라인 비디오 스트리밍 서비스 때문에 DVD 대여점들이 자취를 감추고 있다. 이러한 어려운 상황 속에서, DVD 대여점 주인들은 실낱같은 희망을 잡고자 인기 있는 N개의 DVD들로 구성된 시리즈를 구매한다(각 DVD들은 0번부터 N-1까지 이루어져 있다).

ACM 대여점의 주인 원주연 또한 울며 겨자먹기로 인기 있는 시리즈물을 구매했고, 진열을 하기 위해 맞춤형 선반을 주문제작하였다(맞춤 제작이기 때문에 선반의 번호 또한 0번부터 N-1까지 이루어져 있다). 주연이는 매우 정갈한 사람이기 때문에 DVD를 진열할 때 i번 DVD는 i번 선반에 진열을 한다.

이 시리즈의 열렬한 팬인 민호는 주연이네 대여점에 시리즈가 입고되었다는 소식을 듣고 찾아왔다. 시리즈물은 연속으로 봐야 흥미가 안떨어지기 때문에 민호는 L번부터 R번까지의 DVD들을 빌리려고 한다. 민호는 주연이가 매우 정갈한 성격인 것임을 알기에 주연이를 믿고 실제 DVD들의 번호를 확인하지 않고 L번 선반부터 R번 선반까지 존재하는 DVD들을 들고 카운터에 가져왔다.

그러나, 민호는 간과한 사실이 있다. 주연이네 대여점에는 진상 손님인 진일이가 찾아온다는 것이였다. 진일이는 선반 A에 있는 DVD와 선반 B에 있는 DVD를 서로 바꿔 놓는다. 이러한 진일이의 몰상식한 행동 때문에 민호와 같이 주연이를 믿고 DVD의 번호를 확인 안 하는 선량한 고객들이 피해를 입는 사례들이 속출하였다. 아무 이유가 없는 묻지 마 테러로 인해 가게 매출이 떨어질 위기에 처하자 주연이는 진일이가 보일 때마다 쫓아 냈지만, 시도 때도 없이 찾아오는 진일이의 진상짓을 막기에는 역부족이었다.

이러한 주연이를 보고 안타까운 마음이 든 민호는 주연이를 위해 프로그램을 작성하기로 결심을 한다. 의욕이 넘치는 민호의 마음과는 달리 실력이 따라주지 못해 프로그램의 기능은 조촐하기만 하다. 프로그램의 기능은 다음과 같다.

1. 손님이 L번 선반부터 R번 선반까지에 있는 DVD들을 가져왔을 때 실제로 DVD가 L번부터 R번까지 있나 확인을 해 줄 수 있다.
2. DVD의 순서는 상관이 없다. 예를 들어 손님이 2번 선반부터 4번 선반까지에 있는 DVD를 가져왔을 때 DVD가 2, 3, 4 순서로 진열되어 있건, 4, 2, 3 순서로 진열되어 있건 상관이 없다는 얘기다. 즉 L번부터 R번까지의 DVD가 있으면 된다.

문제의 단순화를 위해 고객이 DVD를 빌려가면, 그 즉시 시청한 뒤 바로 반납한다고 가정한다. 또한 가져다 놓는 위치는 빌리기 전과 동일하다(4, 3, 2 순서로 진열되어 있었으면 다시 4, 3, 2 순서로 진열한다).

 

<입력>
첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. (T ≤ 20 인 자연수)

각각의 테스트 케이스 첫 번째 줄에는 DVD들의 수를 의미하는 정수 N과 대여점에서 일어나는 사건의 수를 의미하는 정수 K 가 주어진다. (1 ≤ N ≤ 100,000 , 1 ≤ K ≤ 50,000)

이어서 대여점에서 일어나는 사건 K 개가 주어진다. 각각의 줄은 세 정수 Q, A, B를 포함한다. (Q는 0 또는 1이고, 0 ≤ A ≤ B < N )

Q는 0 일 때, 진상 손님 진일이가 선반 A의 DVD와 선반 B의 DVD를 서로 바꿔 끼우는 사건을 의미한다. 

Q가 1 일 때는 손님이 선반 A부터 선반 B에 있는 DVD를 카운터에 가져오는 사건을 의미한다. 위에서도 언급했듯이 이 사건이 DVD들의 위치를 바꾸는 일은 일어나지 않는다.

 

<출력>
손님이 DVD를 카운터에 가져왔을 때 손님이 원하는 DVD가 전부 존재하면, (A번 선반부터 B번 선반까지에 있는 DVD를 전부 가져왔을 때 순서에 상관없이 A번 DVD부터 B번 DVD까지 있다면) "YES"를 출력하고, 그렇지 않다면 "NO"를 출력한다.

 

<예제 입력 1>

2
5 8
1 0 4
1 1 2
0 1 3
1 2 2
1 1 3
1 0 0
1 0 2
1 2 4
5 5
0 1 2
0 2 3
0 1 3
1 0 1
1 0 2

<예제 출력 1>

YES
YES
YES
YES
YES
NO
NO
YES
NO

 

---

<풀이 접근>

풀이에 접근하는 것조차 어려웠던 문제입니다. 가장 처음 간단하게 생각해 보았을 때 다음과 같은 접근법을 떠올릴 수 있습니다.
    각 리프 노드에 i번째 선반을 대입하여, dvd가 바뀐 경우 그 번호와의 차를 정수로 기록한다. 부모 노드에서 하위 노드들의 값을 더해 0인지 아닌지로 dvd가 있는지 없는지 확인한다.
그러나 이와 같은 접근의 경우, 자리가 바뀐 여러 dvd 번호와 선반 번호의 차의 합이 우연히 0이 될 수 있어 옳은 접근법이 아닙니다. 그럼 두 번째로 다음과 같은 접근을 생각해 볼 수 있습니다.
    각 노드마다 두 개의 리스트(혹은 set)를 두어 dvd가 바뀐 경우 한 리스트에 새로 들어온 dvd 번호를 양수로 저장하고, 다른 리스트에 잃은 dvd 번호를 음수로 저장하여 두 리스트(혹은 set)를 대조하여 dvd의 득실을 확인한다.
그러나 이는 연산 효율성의 문제로 시간 초과를 보게 됩니다. 적절한 해법이 보이지 않아 구글링을 해보니 다음과 같은 정보를 알게 되었습니다.

정렬되지 않은 어느 수열의 최댓값과 최솟값을 알고 있을 때, 수열의 크기가 (최댓값-최솟값)+1과 같다면, 이 수열에는 최댓값부터 최솟값까지의 모든 수가 있음이 보장된다. 

i번째 리프 노드에는 수열의 i번째 수를 각각 최댓값과 최솟값으로 하여 저장합니다.
확인하고자 하는 구간을 대표하는 노드의 최댓값과 최솟값이 구간의 범위와 일치한다면, 해당 구간에는 빠진 dvd가 없음이 보장됩니다.
위 정보를 토대로 세그먼트 트리를 구현한 코드는 아래와 같습니다.

import sys
import math
input = sys.stdin.readline


def make_tree(tree, start, end, v):
    if start == end:
        tree[v] = start, start
        return
    else:
        mid = (start + end) // 2
        make_tree(tree, start, mid, v * 2)
        make_tree(tree, mid + 1, end, v * 2 + 1)
        tree[v] = tree[v*2][0], tree[v*2+1][1]
    return


def check_tree(tree, start, end, v, left, right):
    if end < left or right < start:
        return True
    elif left <= start and end <= right:
        return left <= tree[v][0] and tree[v][1] <= right
    else:
        mid = (start + end) // 2
        return check_tree(tree, start, mid, v * 2, left, right) and check_tree(tree, mid + 1, end, v * 2 + 1, left, right)


def update_tree(tree, start, end, v, idx, new):
    if idx < start or idx > end:
        return
    if start == end:
        tree[v] = (new, new)
        return
    mid = (start + end) // 2
    update_tree(tree, start, mid, v * 2, idx, new)
    update_tree(tree, mid + 1, end, v * 2 + 1, idx, new)
    tree[v] = min(tree[v*2][0], tree[v*2+1][0]), max(tree[v*2][1], tree[v*2+1][1])
    return


for TEST_CASE in range(int(input())):
    n, k = map(int, input().split())
    arr = [[*map(int, input().split())] for _ in range(k)]
    shelf = [i for i in range(n)]
    seg_tree = [0 for _ in range((1 << math.ceil(math.log2(n + 1))+1) + 1)]
    make_tree(seg_tree, 0, n-1, 1)
    res = ''
    for q, a, b in arr:
        if q == 0:
            update_tree(seg_tree, 0, n - 1, 1, a, shelf[b])
            update_tree(seg_tree, 0, n - 1, 1, b, shelf[a])
            shelf[a], shelf[b] = shelf[b], shelf[a]
        else:
            chk = check_tree(seg_tree, 0, n-1, 1, a, b)
            res += "YES\n" if chk else "NO\n"
    print(res.rstrip())

 

위 코드를 제출한 결과는 아래와 같습니다.

Python 언어 그룹 정답자는 PyPy3 제출자 외에는 없으며, 44명 중 32등입니다.
1등의 코드는 792ms가 나오네요... 대단합니다.

---

<마무리>
문제의 요구조건과 주어진 입력의 상관관계에 대해서 고민해봐야 하는 문제였습니다.
확실히 플래티넘 레벨의 문제들부터는 풀이를 고민할 때에도 평소와 다른 각도에서 해봐야 하는 것 같습니다.
비록 구글링을 통하긴 했지만, 새로운 것을 알게 된 좋은 문제였습니다.