[Java] 백준 1931 회의실 배정

 

문제

회의의 시작시간, 종료시간이 주어질 때 사용할 수 있는 회의의 최대개수를 출력하는 문제.

 

 

풀이 

- 처음엔 문제를 잘못 이해했다.

   - 시작시간이 2 종료시간이 2라고 할 때 시작과 동시에 끝나므로 해당 경우도 갯수에 더해줘야 한다.

   - 또한 (1 2) (2 2) 인 경우나 (2 2) (2 5) 인 경우 2 회의 모두 결과값에 포함될 수 있다.

- 첫번째로 푼 풀이는 다이나믹 프로그래밍이었다.

   - 현재 인덱스에 대해서 이전의 인덱스를 모두 확인하여 최댓값을 구하게끔 했다.

   - 이 경우 O(n^2)이라는 시간 복잡도가 나와 N이 10만인 경우 100억의 연산이 필요하다는 문제가 있었다. 당연히 시간초과가 났다. 

- 두번째로 푼 풀이는 그리디였다.

    - 사실 회의를 최대한으로 하는 횟수는 매우 간단하게 구할 수 있다.

    - 회의가 빨리 끝나는 것을 기준으로 정렬한 뒤에 0번째 회의부터 더해나가는 것이다.

    - 이 로직을 사용하면 O(N)에 풀이할 수 있다.

 

 

 

코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class b1931 {

    static class Schedule {
        int start, end;

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

        @Override
        public String toString() {
            return "Schedule{" +
                    "start=" + start +
                    ", end=" + end +
                    '}';
        }
    }

    public static void main(String[] args) throws IOException {
//        wrongAnswer();
        solution2();
    }

    /* 그리디 [8:00~]
     - 끝나는 시간을 기준으로 오름차순 정렬한 뒤에
     - 차례로 구하면 탐욕법으로 최대 개수를 구할 수 있다.

     - 다음과 같은 경우 답은 3이다.
    3
    2 2
    1 2
    2 3
    */
    static void solution2() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        ArrayList<Schedule> list = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            list.add(new Schedule(start, end));
        }
        Collections.sort(list, new Comparator<Schedule>() {
            @Override
            public int compare(Schedule o1, Schedule o2) {
                if (o1.end != o2.end)
                    return o1.end > o2.end ? 1 : o1.end == o2.end ? 0 : -1;
                return o1.start > o2.start ? 1 : o1.start == o2.start ? 0 : -1;
            }
        });

        int cnt = 1;
        int prev_end = list.get(0).end;
        for (int i = 1; i < N; i++) {
            if (prev_end <= list.get(i).start) {
                cnt++;
                prev_end = list.get(i).end;
            }
        }

        System.out.println(cnt);
    }

    // 다이나믹 프로그래밍 풀이 : 시간초과
    // - 현재 배열방에 대해서 그 전 배열방을 모두 탐색하며 최솟값을 찾아간다.
    // - O(N^2) => O(100_000 * 100_000) => O(10_000_000_000) 100억
    static void wrongAnswer() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        ArrayList<Schedule> list = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            list.add(new Schedule(start, end));
        }
        Collections.sort(list, new Comparator<Schedule>() {
            @Override
            public int compare(Schedule o1, Schedule o2) {
                if (o1.start == o2.start) {
                    return o1.end > o2.end ? 1 : (o1.end == o2.end ? 0 : -1);
                }
                return o1.start > o2.start ? 1 : -1;
            }
        });

        int[] dp = new int[N]; // N번째 회의까지 최대 개수
        Arrays.fill(dp, 1);
        for (int i = 1; i < N; i++) { // 기준
            for (int j = i - 1; j >= 0; j--) { // 탐색 인덱스
                int nextStart = list.get(i).start;
                int prevStart = list.get(j).start;
                int prevEnd = list.get(j).end;
                if (dp[i] <= dp[j]
                        && nextStart >= prevEnd && prevStart != prevEnd) {
                    dp[i] = dp[j] + 1;
                }
            }
        }

        System.out.println(Arrays.stream(dp).max().getAsInt());
    }
}