파이썬 | 백준 | 9576 | 책 나눠주기

 

solution

1. 최소힙을 이용 (b 기준)

2. defaultdict 이용해 이미 나눠준 책인지 확인

 

# 9576, 책 나눠주기
import sys
from collections import defaultdict
import heapq


T = int(sys.stdin.readline())
while T:
    shared = defaultdict(int)
    want = []
    # N개의 서적을 M명에게 나눠줌
    N, M = map(int, sys.stdin.readline().split())
    cnt = 0     # 책 받은 사람 수
    for _ in range(M):
        a, b = map(int, sys.stdin.readline().split())
        heapq.heappush(want, (b, a))

    while want:
        tmp = heapq.heappop(want)
        for i in range(tmp[1], tmp[0]+1):
            # i 책을 받은 사람이 없다면
            if not shared[i]:
                cnt += 1    # 책 받은 사람 수 1 증가
                shared[i] = 1       # i 책 받은 사람 생김
                break

    print(cnt)
    T -= 1

 

문제 출처 www.acmicpc.net/problem/9576

9576번: 책 나눠주기