[BOJ / Java] 1931 - 회의실 배정

문제

백준 1931 회의실 배정

그리디 문제.

그리디 문제는 직관이 많이 요구된다.

규칙을 찾기 위해 손으로 쓰거나 그려 보면서 가능한 경우를 직접 확인해야 한다.

규칙

1. 가장 빠르게 끝나는 회의로 첫 회의를 시작한다.
2. 그 이후 가장 빠르게 시작하는 회의를 배정한다.
3. 2를 반복한다.

주의할 점

주어진 회의 정보를

1. 종료 시간 오름차순
2. 시작 시간 오름차순

순으로 정렬해야 올바르게 풀 수 있다.

입력 예제가 힌트인 셈.

풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

    int n;
    List<List<Integer>> schedules = new ArrayList<>();

    public static void main(String[] args) {
        new Main().run();
    }

    void run() {
        init();
        solve();
    }

    void init() {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        try {
            n = Integer.parseInt(br.readLine());
            for (int i = 0; i < n; i++) {
                st = new StringTokenizer(br.readLine());
                int start = Integer.parseInt(st.nextToken());
                int end = Integer.parseInt(st.nextToken());
                schedules.add(List.of(start, end));
            }
        } catch (Exception ignored) {}
    }

    void solve() {
        schedules.sort(scheduleComparator());
        List<Integer> prev = schedules.get(0);
        int answer = 1;
        List<Integer> tmp;
        for (int i = 1; i < n; i++) {
            tmp = schedules.get(i);
            if (prev.get(1) <= tmp.get(0)) {
                answer++;
                prev = tmp;
            }
        }
        System.out.println(answer);
    }

    Comparator<List<Integer>> scheduleComparator() {
        return Comparator.comparing((List<Integer> schedule) -> schedule.get(1))
                .thenComparing(schedule -> schedule.get(0));
    }
}

배운 점

Comparator 코드 개선

Before

Comparator<List<Integer>> scheduleComparator() {
    return (s1, s2) -> {
        if (!s1.get(1).equals(s2.get(1))) {
            return Integer.compare(s1.get(0), s2.get(0));
        }
        return Integer.compare(s1.get(1), s2.get(1));
    };
}

딱 봐도 중복이 너무 많아보여서 개선할 방법을 찾아봤다.

After

Comparator<List<Integer>> scheduleComparator() {
    return Comparator.comparing((List<Integer> schedule) -> schedule.get(1))
            .thenComparing(schedule -> schedule.get(0));
}

끝.