파이썬 그리디 알고리즘 백준 9876 책 나눠주기

문제

백준이는 방 청소를 하면서 필요 없는 전공 서적을 사람들에게 나눠주려고 한다. 나눠줄 책을 모아보니 총 N권이었다. 책이 너무 많기 때문에 백준이는 책을 구분하기 위해 각각 1부터 N까지의 정수 번호를 중복되지 않게 매겨 두었다.

조사를 해 보니 책을 원하는 서강대학교 학부생이 총 M명이었다. 백준이는 이 M명에게 신청서에 두 정수 a, b (1 ≤ a ≤ b ≤ N)를 적어 내라고 했다. 그러면 백준이는 책 번호가 a 이상 b 이하인 책 중 남아있는 책 한 권을 골라 그 학생에게 준다. 만약 a번부터 b번까지의 모든 책을 이미 다른 학생에게 주고 없다면 그 학생에게는 책을 주지 않는다.

백준이가 책을 줄 수 있는 최대 학생 수를 구하시오.

입력

첫째 줄에 테스트 케이스의 수가 주어진다.

각 케이스의 첫 줄에 정수 N(1 ≤ N ≤ 1,000)과 M(1 ≤ M ≤ 1,000)이 주어진다. 다음 줄부터 M개의 줄에는 각각 정수 ai, bi가 주어진다. (1 ≤ ai ≤ bi ≤ N)

출력

각 테스트 케이스마다 백준이가 책을 줄 수 있는 최대 학생 수를 한 줄에 하나씩 출력한다.

풀이

가장 많은 학생에게 책을 주기 위해서

책 번호가 빠른 순으로 정렬하고 끝나는 번호가 빠른 순으로 정렬한다.

책을 줬다는 것을 나타 내기 위해 nLists를 0으로 책의 개수만큼 초기화 한다.

인덱스를 맞추기 위해 하나 더 만들어 주었다.

이후 책 번호를 순회면서 책 번호의 시작부터 끝까지 이중 반복문을 구성하였다.

해당 인덱스에 대해 nLists의 값이 0이면 책을 줄 수 있는 것이므로 count를 증가시키고 nLists값을 1로 갱신한다.

반복문이 끝나고 count를 출력한다.

 

import sys
testCase = int(sys.stdin.readline().rstrip("\n"))
for i in range(testCase):
    n, k = map(int, sys.stdin.readline().rstrip("\n").split())
    nLists=[0]*(n+1)
    kLists=[[0,0]]
    for i in range(k):
        a, b = map(int, sys.stdin.readline().rstrip("\n").split())
        kLists.append([a,b])
    kLists = sorted(kLists, key=lambda x:x[0])
    kLists = sorted(kLists, key=lambda x:x[1])
    count=0
    for i in range(1, len(kLists)):
        for j in range(kLists[i][0], kLists[i][1]+1):
            if(nLists[j]==0):
                nLists[j]=1
                count+=1
                break
    print(count)