[백준][JAVA] BOJ 1931 회의실 배정

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

1931번: 회의실 배정

 

 

문제 읽기🤔

---

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 1) 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 2) 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

1) 시작시간, 끝나는 시간이 1, 3인 회의가 끝난 후,  3, 5인 회의가 이루어질 수 있다.

2) 시작시간, 끝나는 시간이 1, 1과 같이 정해질 수도 있다.

 

입력

첫째 줄에 회의의 수 1) N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 2) 시작 시간과 끝나는 시간은 (2^32 - 1)보다 작거나 같은 자연수 또는 0이다.

1) 회의의 수 N이 최대 100,000이므로, 단순히 모든 경우의 수를 따지게 된다면 O(n^2), 즉 최악의 경우 100,000^2가 되기 때문에 시간초과가 발생할 수 있다.

2) 2^32 - 1은 4,294,967,295로 unsigned int의 범위에 해당한다. 그러나 자바에는 unisigned int가 존재하지 않으므로 long 타입의 변수에 시간을 저장해야 한다.

 

출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

 

예제 입력

11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14

예제 출력

4

 

 

문제 풀이📝

---

 

Greedy 알고리즘 - 최적의 해 구하기

모든 경우의 수를 살핀다면 필연적으로 시간초과가 발생하게 된다. -> O(n^2)

그렇기 때문에 최적의 해를 찾아 시간복잡도를 줄여야 한다. (Greedy)

일단 예제 입력을 타임 테이블로 시각화 한다면,

이런 식으로 나타낼 수 있다.

파란색으로 나타낸 부분이 바로 최적의 해이다.

회의가 끝나는 시간이 짧을 수록 더 많이 연결할 수 있기 때문이다.

고로 끝나는 시간이 짧은 회의들끼리 연결을 하다보면 회의실을 최대로 사용할 수 있는 회의의 개수를 도출할 수 있다.

예제 입력은 운이 좋게도 끝나는 시간이 오름차순으로 되어있기 때문에 정렬 없이 순차적으로 답을 찾을 수 있지만, 문제에서는 꼭 오름차순으로 주어진다는 조건이 없기 때문에 직접 끝나는 시간을 오름차순으로 정렬해주어야 한다.

	static class Meeting implements Comparable {

        public long start;
        public long end;

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


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

나는 회의의 시작과 끝 시간을 저장할 수 있는 클래스를 선언한 후, compareTo 메소드를 오버라이딩하여 PriorityQueue에 삽입 시 정렬이 될 수 있도록 하였다.

참고로 PriorityQueue는 Heap으로 구현되어 있기 때문에, 정렬 알고리즘의 시간복잡도는 O(nlgn)이 된다.

먼저, 끝나는 시간이 짧을 수록 높은 우선순위를 주도록 했으며,

만약 끝나는 시간이 같은 회의가 존재할 경우에는 시작 시간이 짧을 수록 높은 우선순위를 주도록 했다.

이는 시작시간과 끝나는 시간이 같은 회의가 존재할 경우를 처리하기 위함이다.

예를 들어 입력이 2 2, 1 2 순으로 들어온다고 치자.

시작 시간의 우선순위를 고려하지 않아 2 2, 1 2 순서대로 우선순위 큐에 들어오게 된다면,

2 2 다음에 1 2를 연결할 수가 없어 1 2는 버려지게 된다. 그렇게 되면 올바른 정답을 도출할 수 없다.

시작 시간의 우선순위를 고려하여 1 2, 2 2 순으로 정렬이 되어야 해당 케이스를 놓치지 않을 수 있다.

 

PriorityQueue 출력하기

정렬은 모두 끝났으니, 그대로 원소들을 순회하면서 연결가능한 원소들을 찾아 개수를 세려고 했다.

그러나 왜인지 테스트케이스들을 통과할 수 없었다. 놓친 부분이 있는지 재차 확인했지만 결과는 같았다.

정말 어이없었던 실수를 알아보자.

        // 해당 코드는 테케 통과하지 못함
        // 이유: PriorityQueue를 stream이나 iterator를 통해 순회하려는 경우에는 우선순위가 보장되지 않는다.
        for (Meeting cur : timetable){;
            if (cur.start < prev.end) continue;
            prev = cur;
            cnt++;
        }
        
        // 올바른 PriorityQueue 원소 순회 방법
        Meeting prev = timetable.poll();
        cnt++;
        while (!timetable.isEmpty()) {
            Meeting cur = timetable.poll();
            if (cur.start < prev.end) continue;
            prev = cur;
            cnt++;
        }

PriorityQueue의 원소들에 접근하는 방법이 틀렸었다.

for-each문을 이용하여 큐를 순회한다면 우선순위에 따라 정렬된 값이 아닌 넣은 순서대로 원소에 접근하게 된다.

정렬된 값을 출력하고 싶다면 반드시 poll() 메소드를 이용하여 원소를 꺼내자!!

https://velog.io/@nawhew/PriorityQueue%EB%A5%BC-stream%EC%97%90%EC%84%9C-%EC%82%AC%EC%9A%A9%EC%8B%9C%EC%9A%B0%EC%84%A0%EC%88%9C%EC%9C%84%EB%A5%BC-%EC%9C%A0%EC%A7%80%ED%95%98%EB%8A%94-%EB%B0%A9%EB%B2%95

PriorityQueue를 stream에서 사용시우선순위를 유지하는 방법

 

 

구현🛠️

---

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

public class Main_1931 {

    static class Meeting implements Comparable {

        public long start;
        public long end;

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


        @Override
        public int compareTo(Object o) {
            Meeting other = (Meeting)o;
            // 끝나는 시간이 빠를 수록 높은 우선순위
            if (this.end < other.end){
                return -1;
            }
            // 끝나는 시간이 같다면
            else if(this.end == other.end){
                // 시작하는 시간이 빠를 수록 높은 우선순위
                return Long.compare(this.start, other.start);
            }
            else
                return 1;
        }
    }

    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        PriorityQueue<Meeting> timetable = new PriorityQueue<>();

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            long start = Long.parseLong(st.nextToken());
            long end = Long.parseLong(st.nextToken());

            timetable.add(new Meeting(start, end));
        }

        long cnt = 0;
        Meeting prev = timetable.poll();
        cnt++;
        while (!timetable.isEmpty()) {
            Meeting cur = timetable.poll();
            //System.out.println(cur.start);
            if (cur.start < prev.end) continue;
            prev = cur;
            cnt++;
        }

        // 해당 코드는 테케 통과하지 못함
        // 이유: PriorityQueue를 stream이나 iterator를 통해 순회하려는 경우에는 우선순위가 보장되지 않는다.
        // https://velog.io/@nawhew/PriorityQueue%EB%A5%BC-stream%EC%97%90%EC%84%9C-%EC%82%AC%EC%9A%A9%EC%8B%9C%EC%9A%B0%EC%84%A0%EC%88%9C%EC%9C%84%EB%A5%BC-%EC%9C%A0%EC%A7%80%ED%95%98%EB%8A%94-%EB%B0%A9%EB%B2%95
/*        for (Meeting cur : timetable){
            System.out.println(cur.start);
            if (cur.start < prev.end) continue;
            prev = cur;
            //System.out.println(prev.start + " " + prev.end);
            cnt++;
        }*/

        System.out.println(cnt);
    }
}

 

 

실행 결과✅

---

굿굿