[BaekJoon] 9576 책 나눠주기 (Java)

1.  문제 링크

https://www.acmicpc.net/problem/9576

2.  문제

요약

• 백준이는 필요 없는 서적을 사람들에게 나눠주려고 하는데, 나눠줄 책을 모아보니 총 N권이었습니다.
• 책이 너무 많기 때문에 책을 구분하기 위해 각각 1부터 N까지의 정수 번호를 중복되지 않게 매겨 두었습니다.
• 조사를 해보니 책을 원하는 서강대학교 학부생이 총 M명이었습니다.
• 백준이는 M명에게 신청서에 두 정수 a, b를 적어 내라고 하였는데, 그러면 백준이는 책 번호가 a 이상 b 이하인 책 중 남아있는 책 한 권을 골라 그 학생에게 줍니다.
• 만약 a번부터 b번까지의 모든 책을 이미 다른 학생에게 주고 없다면 그 학생에게는 책을 주지 않습니다.
• 백준이가 책을 줄 수 있는 최대 학생 수를 구하는 문제입니다.
• 입력: 첫 번째 줄에 테스트 케이스의 수가 주어집니다. 각 케이스의 첫 번째 줄에 1보다 크거나 같고 1,000보다 작거나 같은 정수인 N, M이 주어지고 두 번째 줄부터 M개의 줄에 1보다 크거나 같고 N보다 작거나 같은 정수 $a_i, b_i$가 주어집니다.
• 출력: 각 테스트 케이스마다 백준이가 책을 줄 수 있는 최대 학생 수를 한 줄에 하나씩 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static StringBuilder sb = new StringBuilder();
    static Reader scanner = new Reader();

    static int N, M;
    static Student[] students;
    static boolean[] isGiven;

    static void input() {
        N = scanner.nextInt();
        M = scanner.nextInt();
        students = new Student[M];
        isGiven = new boolean[N + 1];

        for(int idx = 0; idx < M; idx++) {
            int start = scanner.nextInt(), end = scanner.nextInt();
            students[idx] = new Student(start, end);
        }
    }

    static void solution() {
        Arrays.sort(students);

        int answer = 0;

        for(int idx = 0; idx < M; idx++) {
            int start = students[idx].startNum, end = students[idx].endNum;

            for(int book = start; book <= end; book++) {
                if(!isGiven[book]) {
                    isGiven[book] = true;
                    answer++;
                    break;
                }
            }
        }

        sb.append(answer).append('\n');
    }

    static class Student implements Comparable<Student> {
        int startNum, endNum;

        public Student(int startNum, int endNum) {
            this.startNum = startNum;
            this.endNum = endNum;
        }

        @Override
        public int compareTo(Student s) {
            if(this.endNum != s.endNum) return this.endNum - s.endNum;
            return this.startNum - s.startNum;
        }
    }

    public static void main(String[] args) {
        int T = scanner.nextInt();
        while(T-- > 0) {
            input();
            solution();
        }

        System.out.print(sb);
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}