Today's Algorithm(2019-03-17)

baekjoon1931. 회의실배정

처음 이 문제를 이해할 때 잘못 이해한 부분이 있었는데요.

단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다.

문제를 푸는데 이것이 가르키는 의미는 다음과 같습니다.

• 4시에 시작해서 4시에 끝나는 것도 하나의 회의의 개수로 취급한다
• 단, 3 5 가 있고 4 4가 있을 때 3 5을 취급하려면 4 4는 무시해야한다. 즉, 회의가 한번 시작하면 중단할 수 없기 때문에 안된다는 것입니다.
• 그렇지만 3 4가 있고 4 4가 있을 때는 2개의 회의를 취급하겠죠!!

 

문제에서 주어진 예시에서 1 4와 5 7과 같이 1씩 간격이 있는 회의가 있길래 동시에 시작한다는게 5 6와 6 7과 같이 붙어있는 경우는 안되는 줄 알았어요.. 제 생각대로 문제를 이해한 탓이겠죠. 2가지 푸는 방법을 말해보려고 합니다. 첫번째는 제 풀이이구요. 두번째는 다른 사람이 푼 더 간단하게 푸는 방식입니다(길이상 입력 부분은 생략할게요).

 

풀이1

• PrioirtyQueue를 만들 때 회의 시작시간이 빠른순, 같다면 끝나는 시간이 빠른 순으로 정렬하였습니다.

• 시간은 0부터 계속 흘러가게 둡니다. 그리고 회의 남은시간(remaining)도 시간에 맞춰 빼줍니다.

  • while문은 회의가 더이상 없고, 회의 남은 시간도 음수일 때 끝납니다.

• 만약 Queue 안에 해당 시간에 시작하는 회의가 있다면 거기서 비교합니다.

  • 시작시간과 끝나는 시간이 같다면(gap == 0) answer을 증감합니다.

  • 그런데 밑에서 일반적으로 시간이 다되서 answer 증감해주는 경우랑 차별두기 위해서(이중 증감을 피하기 위해) flag에 checked = true 로 표시합니다.

  • 그 밑에 분기 if (next.gap < remaining || remaining <= 0) 에서 탐욕법이 드러나는데요. 현재 진행되고 있는 회의가 회의 후보보다 더 늦게 끝날 때(남은 시간이 후보가 더 작을 때) 후보로 회의를 바꿔치기 합니다.

    • 이때도 flag 표시해두어야 합니다. 2 2가 있고 2 3이 있으면 결과적으로 remaining이 1로 바뀌는데 flag는 2 2때문에 true 되어있을 수 있기 때문입니다.

• while문 마지막에 회의 개수 체크할 때는 기존에 체크 안되었고 남은 회의시간이 0인 것을 찾아 증감합니다.

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Queue<Meeting> meetings = getMeetings(n, br);

        int answer = 0;
        int remaining = -1;
        int time = 0;
        while (!meetings.isEmpty() || remaining >= 0) {
            boolean checked = false;

            while (!meetings.isEmpty() && meetings.peek().start == time) {
                Meeting next = meetings.poll();
                if (next.gap == 0) {
                    answer++;
                    checked = true;
                }

                if (next.gap < remaining || remaining <= 0) {
                    remaining = next.gap;
                    checked = false;
                }
            }

            remaining--;
            time++;

            if (!checked && remaining == 0) answer++;
        }

        System.out.println(answer);
    }

솔직히 아이디어는 쉽게 떠올랐는데 제가 미처 생각하지 못한 경우가 있어 여러 우여곡절이 있었습니다. 그래서 다른 사람의 풀이도 찾아보았습니다.

 

풀이2

• 첫번째 풀이와 달리 정렬은 끝나는 시간 먼저, 시작하는 시간 먼저 순으로 정렬합니다.

  • 회의 끝나는 시간이 결국 핵심이기 때문(가장 경우에 가장 유리한 것 → 탐욕법)
  • 끝나는 시간이 같다면 시작시간으로 정렬하는 이유는 예를들어 7 8과 8 8이 있었을 때 끝나는 시간은 같더라도 8 8먼저 계산되면 curTime 이 8로 갱신되기 때문에 7 8이 다음에 오게 되었을 때 answer에 포함되지 못하게 됩니다. 근데 7 8하고 8 8하면 둘 다 되는거니까요.

• curTime 을 두어 만약 다음 회의의 시작시간이 curTime보다 크거나 같을 때(4 4와 같은 시간 커버 가능) curTime 갱신하고 회의개수를 증감시킵니다.

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Queue<Meeting> meetings = getMeetings(n, br);

        int answer = 0;
        int curTime = 0;
        while (!meetings.isEmpty()) {
            Meeting meeting = meetings.poll();

            if (meeting.start >= curTime) {
                curTime = meeting.end;
                answer++;
            }
        }

        System.out.println(answer);
    }

 

시도해볼만한 테스트 케이스

5
0 5
2 2
2 2
3 7
5 8

3
7 7
7 8
8 8

문제의 본질을 잘 안다면 쉽게 풀었을 것이고 아니라면 저처럼 우여곡절을 많이 겪을 것 같습니다. 아직 멀었네요 전..