[BOJ][Python] 백준 9576번: 책 나눠주기

1일 1PS 65일차!

📚 문제

---

골드 2 책 나눠주기

💡 풀이 과정

---

• 공항 문제와 매우 유사하다.
  • 공항 문제에 a 조건이 추가됐다.
• 공항과 똑같이 Union-Find 를 사용해 해결할 수 있다.
• 책 번호 중에서 가장 큰 것부터 채워나간다.
  • 이를 위해 학생들이 받을 수 있는 책의 최소값이 가장 큰 것부터 처리한다.
  • 즉, a 를 우선적으로 내림차순 정렬한다.
• 이후 해당 학생이 가질 수 있는 가장 큰 책부터 처리해나간다.
  • 이는 Union-Find 를 사용해 바로 찾아낼 수 있다.
• 이때 조건에 맞추기 위해 Find(b) 가 a 보다 작으면 a~b 사이의 책이 없으므로 pass 한다.
• 만약 책이 있으면 Union(b - 1, b) 로 Find(b) 가 다음으로 낮은 수가 나올 수 있도록 최신화한다.

📌포인트

---

• sort
  • 처음에는 오름차순으로 정렬해서 애를 먹었다.
  • 문제의 로직을 확실하게 이해하자.
• sys.stdin.readline()
  • 이 역시 input 을 많이 호출하기 때문에 효율이 높은 sys 를 사용하였다.

💻 코드

---

import sys


class UnionFind:
    def __init__(self, n):
        self.data = list(i for i in range(n + 1))
        self.size = n

    def union(self, x, y):
        self.data[self.find(y)] = self.find(x)

    def find(self, x):
        if self.data[x] == x:
            return x
        self.data[x] = self.find(self.data[x])
        return self.data[x]


Testcase = int(sys.stdin.readline())

for _ in range(Testcase):
    N, M = map(int, sys.stdin.readline().split())
    uf = UnionFind(N)
    cnt = 0

    students = []
    for _ in range(M):
        students.append(list(map(int, sys.stdin.readline().split())))

    students.sort(key=lambda x: x[0], reverse=True)

    for a, b in students:
        root = uf.find(b)
        if root < a:
            continue
        uf.union(root - 1, root)
        cnt += 1

    print(cnt)