[JAVA] 백준 1913번 : 회의실 배정

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

1931번: 회의실 배정

---

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

public class Main {
    static int s, e, answer = 0, lastEnd = 0;
    static StringTokenizer st;
    static List<Meeting> schedule;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        schedule = new ArrayList<>();
        while (N-- > 0) {
            st = new StringTokenizer(br.readLine());
            s = Integer.parseInt(st.nextToken());
            e = Integer.parseInt(st.nextToken());
            schedule.add(new Meeting(s, e));
        }
        Collections.sort(schedule);
        for (Meeting s : schedule) {
            if(lastEnd <= s.start){
                answer++;
                lastEnd = s.end;
            }
        }
        System.out.println(answer);
    }

    static class Meeting implements Comparable<Meeting> {
        int start; int end;
        Meeting(int s, int e){
            this.start = s;
            this.end = e;
        }

        @Override
        public int compareTo(Meeting o) {
            if(this.end < o.end) return -1;
            else if(this.end == o.end){
                if(this.start < o.start) return -1;
                else return 1;
            }
            return 1;
        }
    }
}

💡 그리디

• 마치는 시간을 기준으로 오름차순 정렬 (같은 경우 시작 시간이 빠른 순서대로)
  • 반례) 3 / 4 4 / 3 4 / 2 4 => 빠른 순서대로 정렬해야 2 -> 4 후 4 -> 4 인정됨
• 정렬한 회의 앞부터 탐색 적용 -> 그리디 알고리즘

아래 코드의 경우 시간 초과 발생.
➡️ 생각해보니 굳이 사용여부 검사할 필요 없이 회의 끝나는 시간 기준 정렬 후 그리디 알고리즘 사용하면 됨...ㅡ,ㅡ;;
(최선의 답이라고 확신했으니 그 이후부터는 검사하지 않은 건데.. 그리디에 대해 이해를 제대로 해야 할 듯.. 그리고 마치는 시간 기준으로 정리해야 그리디가 적용 가능함. 마치는 시간 순으로 정렬해야 그 앞에 등장할 수 있는 회의에 대해 생각하지 않으므로)

- 시작하는 시간이 같은 회의는 가장 짧은 진행시간을 가진 회의만 남겨놓는다

- dfs 방식으로 탐색할 때, 동일한 첫번째 회의를 공유하는 재귀에서 유효한 used 배열을 만들어서,, 해당 회의가 k번째에서 등장했다면 k번째 미만에선 사용하지 못하게 (탈출 조건) 하고 싶었음

    -> boolean 배열의 idx를 시작 시간으로 하기엔 시간의 범위가 너무 커서 비효율적

    -> 회의의 고유 idx를 사용하자니 회의 시간을 Map으로 저장하는게 애매해짐 (객체로 하기에도 좀...)

    -> 방문 여부도 Map으로 체크하는것을 시도

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

public class Main_1931 {
    static int s, e, answer = 0;
    static StringTokenizer st;
    static Map<Integer, Integer> schedule = new HashMap<>();
    static int[] startTime;
    static boolean[] used;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int sCnt = 0;
        while (N-- > 0) {
            st = new StringTokenizer(br.readLine());
            s = Integer.parseInt(st.nextToken());
            e = Integer.parseInt(st.nextToken());
            if(schedule.containsKey(s)) {
                if (schedule.get(s) > e)
                    schedule.replace(s, e);
                else if(s == e)
                    sCnt++;
                continue;
            }
            schedule.put(s, e);
        }
        startTime = schedule.keySet().stream().mapToInt(i -> i).toArray();
        Arrays.sort(startTime);
        for (int i = 0; i < startTime.length; i++) {
            used = new boolean[startTime.length];
            used[i] = true;
            dfs(i, sCnt+1);
        }
        System.out.println(answer);
    }

    private static void dfs(int idx, int cnt) {
        if (idx == startTime.length - 1) {
            answer = Math.max(answer, cnt);
            return;
        }
        int endTime = schedule.get(startTime[idx]);
        for (int i = idx + 1; i < startTime.length; i++) {
            if (startTime[i] >= endTime && !used[i]) {
                used[i] = true;
                dfs(i, cnt + 1);
            }
        }
        answer = Math.max(answer, cnt);
    }
}