[baekjoon] 백준 9576번(파이썬): 책 나눠주기

문제

9576번: 책 나눠주기

- 백준이는 방 청소를 하면서 필요 없는 전공 서적을 사람들에게 나눠주려고 한다.

- 나눠줄 책을 모아보니 총 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개의 줄에는 각각 정수 a, b가 주어진다. (1 ≤ a ≤ b ≤ N)

알고리즘

- 테스트 케이스를 입력받는다.

- 케이스만큼 반복하여 매 케이스마다 문제를 수행한다.

- 책의 권수와 학생의 수를 입력받는다.

- 구간을 입력받아 리스트 변수에 넣고 구간의 마지막 수를 기준으로 정렬한다.

- 계수 정렬을 통해 남아 있는 책을 확인한다.

- 모든 구간을 반복문을 통해 구간 길이를 확인한다.

- 구간에 책이 있으면 책을 주고 학생수를 카운트한 후 학생에게 책을 줬으므로 반복문을 멈춰준다.

- 반복문이 멈추면 테스트 케이스의 책을 가져간 학생 수를 출력한다.

- 위 과정을 테스트 케이스만큼 반복한다. 

코드

import sys

case = int(sys.stdin.readline())
# 케이스만큼 반복
for _ in range(case):
    n, m = map(int, sys.stdin.readline().split())
    # a, b 구간을 리스트로 받고 b번 기준으로 정렬
    ab = [list(map(int, sys.stdin.readline().split())) for _ in range(m)]
    ab = sorted(ab, key = lambda x: x[1])
    
    # 학생 수 
    cnt = 0
    # 계수 정렬, n + 1권에 책
    chek = [1] * (n + 1)
    
    # 모든 구간을 반복하여 확인
    for a, b in ab:
        # 구간 길이 확인
        for i in range(a, b + 1):
            # 책이 있으면 책을 준다.
            if chek[i] == 1:
                # 책을 줬으므로 0으로 초기화
                chek[i] = 0
                # 학생 수 카운트
                cnt += 1
                # 구간에 있는 학생에게 책을 줬으므로 멈춘다.
                break
                
    # 각 케이스 별로 학생 수를 출력
    print(cnt)

결과

위 코드에서 구간의 길이를 확인하는 반복문에서 print(chek)를 작성하면 구간에 있는 책에 유무를 다음 출력 화면과 같이 확인할 수 있다.

<출력화면>

위 출력 화면을 보게 되면 처음에 모든 구간에 책이 있는 것을 확인할 수 있다. (여기서 계수 정렬을 통해 문제가 수행되므로 0을 무시하는 대신 책을 n+1 권을 만드는 것이다.) 정렬한 구간에서 첫 번째 구간인 1-2를 먼저 확인한다. 1구간에는 책이 있으므로 책을 주고 학생 수를 카운트한다. 따라서 [1, 0, 1] 모양으로 구간의 책을 확인할 수 있다. 그리고 다시 두 번째 구간인 1-2를 확인한다. 1구간에는 책이 없으므로 2구간을 확인하고 2구간에는 책이 있으므로 2구간에 있는 책을 학생에게 줘 학생 수를 카운트한다. 다음 세 번째 구간인 1-2를 확인하는데 1-2구간에는 모두 책이 없으므로 학생에게 줄 책이 없어진다. 구간을 모두 확인했으므로 이때의 테스트 케이스에서 책을 준 학생을 출력한다. 그리고 위 과정을 테스트 케이스만큼 반복한다.

코드를 분석하게 되면 하나의 케이스를 한 번의 반복으로 수행시키는 것을 확인할 수 있다. 그리고 계수 정렬을 통해 구간에 책을 하나씩 배정하고 정렬된 구간에 있는 학생들을 구간별로 책을 나눠주어 학생 수를 카운트한다. 모든 구간을 확인하면 학생 수를 출력하여 문제의 답을 구한다. 위 과정을 테스트 케이스만큼 반복하여 수행하면 된다. 

github

junjange/CodingTest