백준 1931번 : 회의실 배정 (Comparator와 Comparable)

백준 1931번 : 회의실 배정 https://www.acmicpc.net/problem/1931

🤔 문제

각 회의의 시작 시간과 끝나는 시간이 정해져 있을 때, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자

• 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다.
• 회의의 시작 시간과 끝나는 시간이 같을 수 있다.
• 회의 시작과 끝나는 시간은 0 ~ 231-1

🤓 풀이

회의가 끝나는 시간을 기준으로 오름차순 정렬한 후,
전 회의의 시작 시간보다 같거나 늦은 회의만 선택하기 !
** 회의의 시작 시간과 끝나는 시간이 같은 경우는 여러 개여도 모두 선택해야 한다.
end 변수를 0으로 초기화 한 후, 회의들을 탐색하면서 회의의 시작 시간이 end 보다 크거나 같은 경우에만 count를 증가시킨다.

🥵 주의해야 할 테스트케이스

2
2 2
2 1

위의 경우, 끝나는 시간에 대해서만 오름차순 정렬을 하면 (2, 1)의 회의만 선택된다.
하지만 두 회의 모두 선택되어야 하므로, 끝나는 시간이 같은 경우에는 시작 시간이 빠른 순으로 정렬해야 한다.

👩‍💻 전체 코드

import java.io.*;
import java.util.*;

public class Main {

        static class Meeting implements Comparable<Meeting>{
            int start;
            int end;

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

            @Override
            public int compareTo(Meeting o) {
                if(this.end == o.end) return Integer.compare(this.start, o.start);
                return Integer.compare(this.end, o.end);
            }
        }

        public static void main(String[] args) throws IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            int n = Integer.parseInt(br.readLine());
            Meeting[] meetings = new Meeting[n];
            for(int i = 0; i < n; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                meetings[i] = new Meeting(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
            }
            Arrays.sort(meetings);
            int end = 0;
            int cnt = 0;
            for(Meeting meeting : meetings) {
                if(end <= meeting.start) {
                    cnt++;
                    end = meeting.end;
                }
            }
            System.out.println(cnt);
        }
    }

---

📝 Comparator와 Comparable

정렬해야 하는 객체의 클래스를 만들 때마다, 객체를 정렬할 때마다 Comparator와 Comparable 중에 뭘 써야 할지가 헷갈려서 항상 검색을 했다.
다시는 까먹지 않기 위해 정리를 해보자면 ~

1. 클래스를 만들 때는

class MyClass implements Comparable<MyClass> {
	@Override
    public int compareTo(MyClass o) {}
}

2. 이미 있는 클래스의 객체를 정렬할 때는

Arrays.sort(arr, new Comparator<>() {
	@Override
    public int compare(MyClass o1, MyClass o2) {}
}

이렇게 사용하면 된다.

그런데 여기에서 아주 멋진 점이 있다 ..
자바에서 람다식(Lamda)을 사용하게 되면서, 2번의 경우에

Arrays.sort(arr, (o1, o2) -> {});

이렇게 사용할 수 있게 되었고,
심지어 만약 단순히 두 객체의 정수나 char 타입 멤버를 기준으로 정렬하는 경우라면,

Arrays.sort(arr, (o1, o2) -> Integer.compare(o1.a, o2.a));

Arrays.sort(arr, Comparator.comparingInt(o -> o.a));

아래처럼 Comparator에 정의되어 있는 함수를 사용해서 간단하게 표현할 수도 있다.

그리고 또 가끔 헷갈리는 것이 있는데

compareTo(Object o1, Object o2) {}

위와 같은 함수를 사용할 때,
지금 탐색하고 있는 주인공 객체를 o1, 비교 대상을 o2에 넣으면 오름차순 정렬이 된다.
반대로 하면 내림차순 ! 잊지 말자~!