[BOJ] 백준 1931 - 회의실 배정 풀이

1. 문제

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

1931번: 회의실 배정

 

2. 풀이

그리디 알고리즘과 정렬 알고리즘으로 분류되어 있는 문제이다.

처음에는 회의 시작 시간과 회의시간(종료시간 - 시작시간)을 클래스로 만들고 회의 시작 시간으로 정렬한 후 회의 시간이 가장 적은 것부터 개수를 세려고 했는데 잘못된 방법이었다.

이 문제의 핵심은 회의 종료시간을 기준으로 정렬한다는 것이다.

이해를 돕기 위해 한 블로그 분의 정리된 글에서 사진을 인용하였다. 
이 사진은 입력으로 주어진 회의 시간을 종료 시간에 맞춰 오름차순으로 정렬한 것이다.

단!! 이 예제에서는 종료 시간이 같은 입력이 없지만, 종료시간이 같은 경우가 존재한다면 그때는 오름차순으로 정렬해주어야한다.

3
8 8
1 4
4 8

예를 들어 (8 8), (1, 4), (4, 8)의 입력이 주어졌다면, 종료 시간만으로 정렬하면 (1, 4), (8, 8), (4, 8)로 정렬된다. 이러면 결과 값이 (1, 4), (8, 8)로 2개가 된다. 따라서 종료시간이 같다면 오름차순으로 정렬해주어야 하는 것이다.

정렬을 마쳤다면 이제 로직에 들어가보자.
종료 시간에 맞춰 오름 차순으로 정렬하면 리스트의 첫 번째 인덱스의 회의는 무조건 선택된다. 그 후 인덱스를 저장할 변수를 하나 두어(idx), 이 인덱스에 맞는 객체의 종료시간이 반복문으로 선택된 객체의 시작시간보다 작거나 같다면 회의를 선택하는 경우가 되고 idx에 그 때의 선택된 객체의 인덱스를 넣어준다.

 

3. 소스 코드

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

public class Main {
    static class Meeting {
        int start;
        int end;

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

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        List<Meeting> list = new ArrayList<>();
        int result = 1;

        int N = Integer.parseInt(br.readLine());
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            list.add(new Meeting(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken())));
        }

        Collections.sort(list, new Comparator<Meeting>() {
            @Override
            public int compare(Meeting o1, Meeting o2) {
                if (o1.end == o2.end) {
                    return o1.start - o2.start;
                }
                return o1.end - o2.end;
            }
        });

        int idx = 0;
        for (int i = 1; i < list.size(); i++) {
            if (list.get(idx).end <= list.get(i).start) {
                result += 1;
                idx = i;
            }
        }

        bw.write(Integer.toString(result));
        bw.flush();
        bw.close();
        br.close();
    }
}

* 사진 출처 : https://st-lab.tistory.com/145

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