[백준] 1931번 : 회의실 배정 - 자바(Java)

Problem 🔒

문제

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

 

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

예제 입력 1

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

예제 출력 1

4

---

Approach 1 ⭕ - 완전 탐색

모든 회의의 조합을 탐색하는 완전 탐색(브루트포스)방식이 있다.

이 방식은 모든 회의에 대해 선택/제외의 모든 경우를 탐색하므로 시간 복잡도가 $O(2^N)$으로 가장 최악의 접근이다.

1. 각 회의를 선택하거나 제외하는 모든 경우를 탐색한다. (재귀 사용)
2. 각 부분 집합의 조건(회의 시간이 겹치는지)을 확인 후, 최대 회의 개수를 구한다.

for (int i = 0; i < N; i++) {
    meetings[i][0] = sc.nextInt(); // 시작 시간
    meetings[i][1] = sc.nextInt(); // 종료 시간
}
find(0, 0, 0); // 초기값: index, 종료 시간, 선택한 회의 개수
System.out.println(maxCount); // 최대 회의 개수 출력
// 재귀를 활용해 모든 조합의 경우를 검사
static void find(int index, int endTime, int count) {
    if (index == N) {
        maxCount = Math.max(maxCount, count);
        return;
    }
    // 회의를 선택하지 않는 경우
    find(index + 1, endTime, count);
    // 회의를 선택하는 경우 (종료 시간이 겹치지 않을 때만)
    if (meetings[index][0] >= endTime) {
        find(index + 1, meetings[index][1], count + 1);
    }
}

---

Approach 2 ⭕ - 그리디

그리디 접근법으로 선택 가능한 회의들 중 종료 시간이 가장 빠른 회의를 선택한다.

위의 방법이 맞는지 검증하기(귀류법)

귀류법 : 명제가 거짓이라고 가정하고 모순을 찾아 명제가 참임을 증명하는 방법이다.

• 명제 : 선택 가능한 회의들 중 종료 시간이 가장 빠른 회의 A1을 선택하는게 최적 해이다.
• 명제가 거짓이라면 : A1말고 다른 회의를 선택하는 것이 최적 해이다.
  • 다른 회의 B를 선택하면 회의의 최대 개수는 4개(B, 노랑)이다.
  • 회의 A1을 선택하면 회의의 최대 개수는 5개(A1, A2, 노랑)이므로 모순이 있다.
  • 따라서 명제는 참이 된다!!

Solution Process 📝

1. 회의 정렬
   • 회의의 시작 시간을 기준으로 정렬하고, 시작 시간이 같다면 종료 시간 기준으로 오름차순으로 정렬한다.
   • 종료 시간 기준으로 정렬하지않으면, 최적의 해를 찾지 못한다.
     • 문제에서 회의 시작시간과 끝나는 시간이 같을 수도 있다고 주어져서, 시작하자마자 바로 끝나는 회의도 있기 때문이다.
2. 회의 배정(그리디 알고리즘)
   • while문을 통해 회의를 탐색하면서, 가능한 회의 중 종료 시간이 가장 빠른 회의를 선택한다.
   • 다음 회의를 선택하면 flag를 true로 변경해 반복을 계속 진행하고, 선택한 회의가 없으면 false 처리되어 반복을 종료한다.
   • 조건 1 : 현재 회의 시작 시간이 가장 빠른 종료시간보다 크거나 같은 경우
     • 현재 회의의 인덱스부터 다음 탐색을 시작하도록 인덱스를 업데이트한다.
     • 회의를 선택했으므로 flag를 true로 변경해 반복을 진행한다.
     • break로 다음 탐색으로 넘어간다.
   • 조건 2 : 현재 회의 종료 시간이 min보다 작아 더 빨리 끝나는 회의가 발견된 경우
     • mim 값을 해당 회의 종료 시간으로 갱신한다.
   • 회의를 선택한 경우 배정한 회의 개수를 증가시키고, min 값을 초기화한다.

---

Approach 3 ⭕ - 더 간결한 그리디 ⭐

1. 회의 정렬
   • 회의를 정렬할 때, 종료 시간 기준으로 먼저 정렬하고 시작 시간을 정렬한다.
   • 이전 방법에서는 가장 빨리 끝나는 회의를 찾느라 더 코드가 복잡해졌는데, 이 방법으로 풀면 가장 빨리 끝나는 회의를 찾을 필요가 없어 시작 시간만 비교해주면 된다.
2. 회의 배정(그리디 알고리즘)
   • 현재 회의의 시작 시간이 이전 회의의 종료시간보다 이르면 회의를 배정할 수 없어서 넘어간다.
   • 배정한 회의 개수를 증가시키고, 현재 회의 종료 시간을 저장한다.

알게된 점 😯

2차원 배열 정렬 방법에 대해 체득할 수 있었다!

Arrays.sort(room, (a,b)->{ if(a[0]==b[0]) return (a[1]-b[1]); return (a[0]-b[0]); });

---

Solution 💡

그리디1 : 시작 시간 정렬 후 종료 시간 정렬

public class 그리디 {
    static int N, room[][];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        room = new int[N][2];
        for(int i=0; i<N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            room[i][0] = Integer.parseInt(st.nextToken());
            room[i][1] = Integer.parseInt(st.nextToken());
        }
        // 회의는 {시작시간, 끝시간} 2개의 값을 가지는 배열이고,
        // 회의 2개의 시작시간(a[0], b[0])을 비교하여 오름차순으로 정렬한다.
        // 시작 시간이 같으면 끝나는 시간도 오름차순으로 정렬한다.
        Arrays.sort(room, (a,b)->{
            if(a[0]==b[0]) return (a[1]-b[1]);
            return (a[0]-b[0]);
        });

        int cnt = 0; // 배정된 회의 개수
        int idx = 0; // 다음 탐색을 시작할 회의 인덱스
        int min = Integer.MAX_VALUE; // 가장 빠른 종료 시간을 저장할 변수
        boolean flag = true; // 반복문 제어
        while(flag){
            flag = false;
            for(int i=idx; i<N; i++){
                // 현재 회의 시작시간이 가장 빠른 종료시간보다 크거나 같은 경우
                if(room[i][0]>=min) {
                    idx = i;
                    flag = true;
                    break;
                }
                // 더 빨리 끝나는 회의가 발견된 경우
                if(min>room[i][1]){min = room[i][1];}
            }
            cnt++;
            min = Integer.MAX_VALUE; // 초기화
        }
        System.out.println(cnt);
    }

}

그리디2 : 종료 시간 정렬 후 시작 시간 정렬

public class 그리디 {
    static int N, room[][];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        room = new int[N][2];
        for(int i=0; i<N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            room[i][1] = Integer.parseInt(st.nextToken()); // 시작 시간
            room[i][0] = Integer.parseInt(st.nextToken()); // 종료 시간
        }
        // 종료 시간으로 먼저 정렬 후, 시작 시간 정렬
        Arrays.sort(room, (a,b)->{
            if(a[0]==b[0]) return (a[1]-b[1]);
            return (a[0]-b[0]);
        });

        int cnt = 0; // 배정된 회의 개수
        int t = 0;
        for(int i=0; i<N; i++){
		        // 종료시간이 시작시간보다 크면 패쓰
            if(t>room[i][1]) continue;
            cnt++;
            t = room[i][0];
        }
        System.out.println(cnt);
    }
}

Reference 📄

https://blog.encrypted.gg/975