[백준]1931- 회의실 배정 문제 풀이(Java,자바)

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

 

들어가며

이 문제는 테스트 케이스를 잘보면 쉽게 실마리를 잡을 수 있다.

코드

package solved.ac.class3;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;

public class 백준1931_회의실배정 {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());
        Meeting[] meetings = new Meeting[n];
        for (int i = 0; i < n; i++) {
            int[] inputs = Arrays.stream(reader.readLine().split(" "))
                    .mapToInt(Integer::parseInt)
                    .toArray();
            Meeting meeting = new Meeting(inputs[0], inputs[1]);
            meetings[i] = meeting;
        }

        Arrays.sort(meetings, Comparator.comparingInt((Meeting m) -> m.end)
                .thenComparingInt(m -> m.start));

        int count = 0;
        int lastEndTime = 0;

        for (Meeting meeting : meetings) {
            if (meeting.start >= lastEndTime) {
                count++;
                lastEndTime = meeting.end;
            }
        }

        System.out.println(count);
    }

    static class Meeting {
        int start;
        int end;

        public Meeting(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }
}

풀이

먼저 테스트 코드를 잘 보자.

오른쪽 값들은 회의가 끝나는 시간이다.

오름차순으로 정렬이 되어 있다.

그러면 이 상태에서 만들어진 배열에서 회의 일정을 어떻게 잡을 수 있을까?

(1,4),(5,7),(8,11),(12,14) 로 진행된다.

 

1 4
5 7
3 8
3 5
2 13
5 9
0 6
8 11
8 12
6 10
12 14

위 값을 입력받는다고 할 땐 어떻게 접근해야 할까??

정답은 여기서 유추를 할 수 있다.

끝나는 시간으로 정렬을 하게 되면 자연스럽게 답을 구할 수 있게 된다.

왜냐하면 최대 개수를 구한다는 말은 최대한 일정을 많이 잡아야 한다.

그러면 중간에 텀이 생기면 안되고, 이 때문에 끝나는 시간으로 정렬하고 계산하면 된다.