[자바/그리디] 코드트리. 회의실 준비 구현

문제

링크

해석

이 문제는 그리디를 연습하기 위한 문제로, 그리디 로직을 구성하는 기준에 따라 그리디를 적용할 수 있고 없고가 존재함을 이해할 수 있었다.

회의실을 최대한 많이 잡아야 하는 문제인데, 고려해야 하는 요소가 두 가지이다. 회의 시간이 짧은 것으로 최대한 골라야 많은 회의를 잡을 수 있으며, 겹치지 않도록 시작 시간과 끝 시간을 검사해야 한다.

이 두 가지를 동시에 고려하면서 그리디하게 풀어내기 위해서는 회의가 끝나는 시간을 기준으로 오름차순 정렬을 해야 한다. 이 지점만 캐치할 수 있으면 로직은 어렵지 않다.

코드

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());
        int[][] arr = new int[n][2];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
        }

        String ans = solution(n, arr);

        bw.write(ans);

        br.close();
        bw.flush();
        bw.close();
    }

    private static String solution(int n, int[][] arr) {
        final int START = 0;
        final int END = 1;

        Arrays.sort(arr, (o1, o2) -> {
            if (o1[END] == o2[END]) {
                return o1[START] - o2[START];
            }
            return o1[END] - o2[END];
        });

        int cnt = 0;
        int prevEnd = 0;
        for (int[] meeting : arr) {
            if (prevEnd <= meeting[START]) {
                prevEnd = meeting[END];
                cnt++;
            }
        }

        return String.valueOf(cnt);
    }

}

레슨런

알고리즘은 로직 구현 전에 설계하는 부분이 상당히 중요함을 다시금 느낄 수 있었다. 충분히 고민하고 손으로 짜보고 나서는, 로직을 실제로 구현하는 건 금방 걸리니까 '잘' 고민하고, '잘' 구현하자.