백준(BaekJoon) 9576번 : 책 나눠주기 - python 문제 풀이

❓9576번 : 책 나눠주기

〽️ 문제 요약

M명의 학생들이 범위 (a, b) (1 ≤ $a_i$ ≤ $b_i$ ≤ N)를 정할 때 책 번호가 a 이상 b 이하인 책 중 남아있는 책 한권을 학생에게 주는 경우 책을 줄 수 있는 최대 학생 수를 구하면 되는 문제

🤨 접근법

그리디하게 작은 시작 범위를 가진 학생들부터 책을 줘보자

시작 범위를 기준으로 정렬 후 앞 번호부터 줄 수 있는 책의 번호를 준다.

위와 같은 예제의 경우 첫 번째 학생에게 1을 주고, 두 번째 학생에게 2를 주게되어 2명에게 줄 수 있다. 문제는 없어 보인다.

다만 아래와 같은 경우를 살펴보면,

3  3
1  2
1  3
2  2

작은 시작 범위를 가진 학생들에게부터 순서대로 책을 주게 되면 첫 번째 학생이 1, 두 번째 학생이 2를 받고 세 번째 학생이 책을 받지 못한다.

하지만 첫 번째 학생이 1, 두 번째 학생이 3, 세 번째 학생이 2를 받게 되면 모두 책을 받을 수 있게 된다.

즉, 뒤의 책 번호를 받아도 되는 학생에 앞의 책을 받게 된다면 앞의 책을 받을 수 있는 뒤의 학생이 책을 못받게 된다. 따라서 끝 범위를 기준으로 정렬 후 순서대로 책을 주어야 한다. 위의 경우 끝 범위를 기준으로 정렬하게 되면 다음과 같다.

1  2
2  2
1  3

이제 앞 번호부터 순서대로 학생에게 책을 주게 되면 3명의 학생이 책을 받을 수 있다.

🔡 코드

import sys

input = sys.stdin.readline

T = int(input())
for _ in range(T):
    N, M = map(int, input().rstrip().split())
    scopes = sorted([list(map(int, input().rstrip().split())) for _ in range(M)], key = lambda x : x[1])
    visited = [False for _ in range(N+1)]
    count = 0
    for a, b in scopes:
        for i in range(a, b+1):
            if not visited[i]:
                visited[i] = True
                count += 1
                break

    print(count)

sorted함수의 key 인자에 lambda식을 활용해 끝 범위를 기준으로 정렬하였다. 정렬된 범위들을 순회하며 범위 내 탐색되지 않은 수를 방문하게 되면 count해준 뒤 방문처리 해주어 해당 책이 이미 배정되었음을 표시하고 다음 순회때 방문하지 않게 한다.