[백준] 1931번 : 회의실 배정 – JAVA [자바]

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

1931번: 회의실 배정

 

---

• 문제

 

 

---

• 문제 풀이

백준 1931번 회의실 배정은 실버 1 난이도의 그리디 및 정렬 문제이다. 항상 그리디 문제들을 공부하고 풀어야지 풀어야지 생각만 했다가 학교에서 CSE2310 Algorithm Design이라는 과목에서 그리디 알고리즘에 대해 배우고 시험도 끝난 다음에 드디어 문제들을 조금 풀게 되었다.

 

이 문제는 그리디에서 가장 기본적인 문제인 거 같다. 학교에서도 그리디를 처음 배울 때 접했던 문제가 이런 문제였다. 학교에서 배울 때 이런 문제를 'Interval Scheduling'이라고 한다고 배웠다. 이 문제에서는 회의실 n개와 각각 회의실마다 시작 시간이랑 종료 시간이 주어졌을 때 안 겹치게 하는 선에서 참여할 수 있는 최대 회의실의 개수를 구하면 된다.

 

이 문제는 그리디의 대표 유형이므로 확실히 알고 가는 게 좋을 거 같다 (학교에서도 알고리즘 시험을 볼 때 이런 비슷한 문제가 하나씩은 무조건 나왔다. 그래서 중요하다고 생각한다). 

 

이 문제의 설명은 밑에 있는 블로그 글에서 설명을 기가 막히게 해 줬다. 참고하면 되겠다.

 

https://st-lab.tistory.com/145

[백준] 1931번 : 회의실배정 - JAVA [자바]

 

우선 이런 그리디 문제들을 풀 때 중요한 것은 정렬하는 거라고 생각한다. 결국에는 회의실을 어떤 기준을 토대로 정렬한 다음에 풀면 되기 때문이다.

 

이 문제에서 중요한 부분은 바로 겹치지 않는다는 것이다. 결국에 회의 1과 회의 2가 겹치지 않으려면 회의 1의 종료 시간이 회의 2의 시작 시간보다 작거나 같아야 한다. 이렇게 회의들이 겹치지 않게 한 상태에서 최대한 많은 회의를 선택하려면 종료시간이 빠른 것부터 선택해야 한다. 따라서, 서로 겹치지 않는 회의에 대해 종료시간이 빠르면 더 많은 회의들을 선택할 수 있는 시간이 많아진다는 것이다.

 

우선 왜 시작시간을 기준으로 정렬하면 안 되는지를 보여주겠다. 다음과 같은 그림을 예시로 들겠다.

 

이 그림에서 밑에 있는 게 시작 시간이 더 빠르지만 종료 시간이 위에 있는 4개보다 늦게 끝나면 4개를 고를 수 있는 상황에서도 1개밖에 고르지 못하게 된다. 따라서, 시작 시간을 기준으로 정렬하면 맞는 답을 구할 수 없다.

 

 

그다음에는 한 회의의 인터벌 (interval), 즉 (종료 시간 - 시작 시간)을 기준으로 정렬을 하면 다음과 같이 될 수도 있다.

 

이 그림에서 볼 수 있듯이 인터벌이 긴데 시작 시간이 더 빠르면 2개를 고를 수 있는 상황인데 인터벌이 짧은 것부터 고르면 1개밖에 고르지 못하게 된다.

 

이 간단한 예시들을 봤을 때 종료시간을 기준으로 정렬을 하는 게 맞다고 다시 한번 확인할 수 있다.

 

 

이제 어떻게 코드를 짰는지에 대해서 설명해 보겠다.

 

우선 회의실 클래스를 만들어줬다. 이 클래스를 MeetingRoom이라고 하고 그리고 아래에 있는 코드를 보면 알 수 있듯이 클래스를 선언할 때 다음과 같이 했다.

 

static class MeetingRoom implements Comparable<MeetingRoom>

 

이 이유는 회의실 Object를 담은 배열을 정렬할 때 쓰기 위함이다. 우선 회의실은 시작 시간과 종료 시간을 필드로 갖는다.

 

Comparable을 implements 해주면 Comparable interface에 있는 compareTo 함수를 override 해줘야 한다. 종료 시간이 빠른 순으로 정렬을 하기 위해서는 다음과 같이 해주면 된다.

 

@Override
public int compareTo(MeetingRoom o) {
    return endTime - o.endTime;
}

 

하지만 종료 시간이 같을 때 시작 시간이 더 빠른 걸로 하면 더 많은 회의를 참석할 수 있으므로 다음 조건도 추가해 준다.

 

@Override
public int compareTo(MeetingRoom o) {
    if (endTime == o.endTime) return startTime - o.startTime;
    return endTime - o.endTime;
}

 

자세한 코드는 아래에 있는 코드를 참고하면 되겠다.

 

 

---

• 코드

 

import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        MeetingRoom[] arr = new MeetingRoom[n];  //회의실 배열
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int startTime = Integer.parseInt(st.nextToken());
            int endTime = Integer.parseInt(st.nextToken());
            arr[i] = new MeetingRoom(startTime, endTime);
        }
        Arrays.sort(arr);  //회의실을 종료 시간을 기준으로 정렬
        int count = 0;
        int time = 0;  //현재 시간
        for (int i = 0; i < n; i++) {
        //만약에 현재 시간이 i번째 회의 시작 시간보다 작거나 같으면 포함시킨다
            if (time <= arr[i].startTime) {  
                count++;
                time = arr[i].endTime;  //그리고 현재 시간은 i번째 회의가 끝난 시간이 된다
            }
        }
        System.out.print(count);
    }

    static class MeetingRoom implements Comparable<MeetingRoom> {  //회의실 클래스
        int startTime;  //시작 시간
        int endTime;  //종료 시간

        public MeetingRoom(int startTime, int endTime) {
            this.startTime = startTime;
            this.endTime = endTime;
        }


// 종료 시간을 내림차순으로 정렬하고 종료 시간이 같으면 시작 시간이 더 빠른게 앞으로 온다.
        @Override
        public int compareTo(MeetingRoom o) {
            if (endTime == o.endTime) return startTime - o.startTime;
            return endTime - o.endTime;
        }
    }
}