[JAVA]BOJ 1931, 회의실 배정

정렬과 그리디 알고리즘을 사용한 문제이다. 그리디 알고리즘은 매 단계마다 최선의 선택을 하는 방법을 말한다. 난 처음에 그리디 알고리즘 문제인지 모르고 모든 가지수를 다 선택하는 방식을 재귀로 짰더니 시간초과가 났다. 그리디 알고리즘인 걸 알고 고쳤더니 통과했다!

 

1. 끝나는 시간을 기준으로 정렬을 한다.

1-2. 만약 끝나는 시간이 같다면, 시작 시간이 빠른 것이 먼저 온다.

2. 첫 번째 회의를 선택하고, 그 다음으로 선택 가능한 회의를 선택한다.

3. 2번을 계속 반복해서 모든 회의를 다 살펴본다.

 

단순하다.. 이렇게 적으니까.. 그리디 알고리즘이라서 가능한거다.

 

1. 1-2. 정렬하기

사용자 정의 클래스를 하나 만든다. 나는 Meeting이라고 만들었다. Meeting 클래스는 start(시작시간), end(끝나는시간), term(회의시간 = 끝나는시간 - 시작시간) 세 개의 필드를 가진다.

그리고 Meeting을 정렬할 것이므로 정렬방법을 오버라이딩해준다. 

public class Meeting implements Comparable<Meeting>{
    private int start;
    private int end;
    private int term;

    // 생성자 생략

    @Override
    public int compareTo(Meeting o) {
        if(end == o.end) // 끝나는 시간이 같으면
            return start - o.start;
        return end - o.end;
    }

    // getter 생략
}

 

2. 3. 회의 선택하기

회의를 선택하는 방법은, 다음에 선택할 회의의 끝나는 시간(end)과, 이전에 선택된 회의의 끝나는 시간(end), 그리고 다음에 선택할 회의시간(term)을 비교하는 것이다. 예를 들면

 

순서대로 start, end, term이다.

    1 5 4 --> 선택
    4 6 2 --> 6(선택할 회의의 end) - 5(이전에 선택된 회의의 end) = 1 이고 term은 2, 2 <= 1 을 만족하지 않으므로 선택하지 않음 
    5 10 5 --> 10 - 5 = 5, term은 5, 5 <= 5 을 만족하므로 선택
    답 : 2

 

이런 방식으로 최적의 선택을 하고, 끝까지 모든 회의를 봤을때, 선택된 회의의 개수가 최선의 경우이다.

 

이 문제의 또 다른 함정은 (2, 2) (2, 2) (2, 2) 인 경우에 다 같은 회의니까 1이 나와야 할 것 같지만 답은 3이라는 것이다.. 질문계시판에 반례가 많이 있고 다 확인해보면 된다. 근데 위 알고리즘으로 풀면 사실 다 적용되긴한다.

i = 0; // i는 이전에 선택된 회의의 인덱스
for(j=1;j<N;j++){
    if(meetings[j].getTerm() <= (meetings[j].getEnd() - meetings[i].getEnd())) {
        cnt++;
        i = j; // 회의를 선택했으므로 i를 바꿔줌
    }
}

---

아래는 전체 코드이다.

public class Meeting implements Comparable<Meeting>{
    private int start;
    private int end;
    private int term;

    public Meeting() {
    }

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

    @Override
    public int compareTo(Meeting o) {
        if(end == o.end) // 끝나는 시간이 같으면
            return start - o.start;
        return end - o.end;
    }

    public int getStart() {
        return start;
    }

    public int getEnd() {
        return end;
    }

    public int getTerm() {
        return term;
    }
}

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BOJ1931 {
    public static void main(String[] args) throws IOException {
        // 사용자 정의 클래스 하나 만들고, start, end, term(차이) 필드 3개 주기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N, i, j, start, end, cnt = 1;
        String str;
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        Meeting[] meetings = new Meeting[N];

        // 입력
        for(i=0;i<N;i++){
            str = br.readLine();
            st = new StringTokenizer(str);

            start = Integer.parseInt(st.nextToken());
            end = Integer.parseInt(st.nextToken());
            meetings[i] = new Meeting(start, end, end - start);
        }

        // end를 기준으로 정렬
        Arrays.sort(meetings);

        // 그리디 알고리즘으로 풀기!!
        // meetings[0]은 이미 선택함 -> [1]부터 확인하기
        i = 0;
        for(j=1;j<N;j++){
            if(meetings[j].getTerm() <= (meetings[j].getEnd() - meetings[i].getEnd())) {
                cnt++;
                i = j;
            }
        }

        System.out.println(cnt);
    }
}

---

반례들 예시

 

    [0] 1 4 = 3 
    [1] 3 5 = 2 > 1
    [2] 0 6 = 6 > 2
    [3] 5 7 = 2 <= 3(7 - 4) 보다 작거나같음
    [4] 3 8 = 5 > 1
    [5] 5 9 = 4 > 2
    [6] 6 10 = 4 > 3
    [7] 8 11 = 3 <= 3 보다 작거나같음
    [8] 8 12 = 4 > 1
    [9] 2 13 = 11 > 2
    [10] 12 14 = 2 <= 3 보다 작거나같음



    1 2 = 1
    2 2 = 0 <= 2 - 2
    답 : 2

    1 1 = 0
    1 2 = 0 <= 2 - 2
    답 : 2

    2 2 = 0
    2 2 = 0
    2 2 = 0
    답 : 3

    1 5
    4 6
    5 10
    답 : 2

    4 4
    3 4
    2 4
    답 : 2