[백준][코틀린] 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개의 줄에는 각각 정수 ai, bi가 주어진다. (1 ≤ ai ≤ bi ≤ N)

출력

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

예제 입력	예제 출력
1 2 3 1 2 1 2 1 2	2

문제 풀이

2022.02.12 - [Algorithm/with Kotlin] - [백준][코틀린] 1931 회의실 배정

위 문제랑 비슷한 문제다! 정렬을 해줄 때, 끝나는 범위를 기준으로 정렬을 해준다. Boolean 배열을 쓰지 않고 풀고 싶었는데,, 불가능하다는걸 깨달았다...책을 나눠줬는지 확인하고 나눠주지 않았다면 나눠주면 된다!

</>̆̈ 코드

import java.util.*

fun main() {
    val br = System.`in`.bufferedReader()
    repeat(br.readLine().toInt()) {
        val (n, m) = br.readLine().split(" ").map { it.toInt() }
        val books = mutableListOf<Pair<Int, Int>>()
        val checks = BooleanArray(n+1); var result = 0
        repeat(m) {
            StringTokenizer(br.readLine()).run {
                books.add(Pair(nextToken().toInt(), nextToken().toInt()))
            }
        }
        books.sortWith(compareBy({it.second}, {it.first}))

        for (book in books) {
            for (number in book.first .. book.second) {
                if (!checks[number]) {
                    result++; checks[number] = true; break
                }
            }
        }

        println(result)
    }
}

링크

9576번: 책 나눠주기