문제

강의의 시작 시간과 종료 시간을 참고해서 최대한 적은 수의 강의실을 사용하여 강의를 해야 할 때 최소 강의실 수는?

예제

코드

시도1 - X

내 힘으로 작성했지만 시간 초과로 실패한 코드다.

입력 값들을 Lecture로 만들고 PriorityQueue에 시작 시간 오름차순으로 정렬한다.
- 이때 이유는 모르겠지만 시작 시간 오름차순 정렬이 되지 않아서 lectures[i]에 값을 넣고 Arrays.sort()로 정렬한 후 PriorityQueue에 삽입하는 방식을 사용했다.
- 이 과정에서 불필요한 시간이 사용돼서 시간 복잡도가 높아졌다.
PriorityQueue가 빌 때까지 아래 연산을 반복한다.
- PriorityQueue에서 Lecture를 poll()한다.
- 종료 시간 <= 모든 시작 시간을 계산하여 true가 나오면 PriorityQueue에서 remove()한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.PriorityQueue;
import java.util.Arrays;

public class _1374 {
    private static class Lecture implements Comparable<Lecture> {
        int no, start, end;
        boolean isRemoved = false;

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

        @Override
        public int compareTo(Lecture o) {
            return this.start - o.start;
        }
    }

    public static void main(String [] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PriorityQueue<Lecture> pq = new PriorityQueue<>();

        int N = Integer.parseInt(br.readLine());
        Lecture[] lectures = new Lecture[N];

        for (int i = 0; i < N; i++) {
            String input = br.readLine();

            // StringTokenizer를 사용하여 문자열을 공백으로 분리
            StringTokenizer tokenizer = new StringTokenizer(input);

            // 각 토큰을 정수로 변환
            int lecnum = Integer.parseInt(tokenizer.nextToken());
            int lecstart = Integer.parseInt(tokenizer.nextToken());
            int lecend = Integer.parseInt(tokenizer.nextToken());
            lectures[i] = new Lecture(lecnum, lecstart, lecend);
        }

        Arrays.sort(lectures);
        for (int i = 0; i < N; i++) {
            pq.add(lectures[i]);
        }

        int result = 0;
        while (!pq.isEmpty()) {
            Lecture lec = pq.poll();
            int end = lec.end;
            lec.isRemoved = true;
            result += 1;
            for (Lecture lecture : lectures) {
                if (!lecture.isRemoved && end <= lecture.start) {
                    lecture.isRemoved = true;
                    pq.remove(lecture);
                    end = lecture.end;
                } 
            }
        }
        System.out.println(result);
    }

}

매우 비효율적이고 ... 가독성도 좋지 않다 ....ㅠㅠㅠㅠ
열심히 풀었는데..

시도2 - O

도저히 모르겠어서 다른 사람 코드를 보고 분석했다 ..

입력 값들을 Lecture로 만들고 PriorityQueue에 시작 시간 오름차순으로 정렬한다.
PriorityQueue가 빌 때까지 아래 연산을 반복한다.
- endTimeQueue를 선언한다.
- PriorityQueue에서 Lecture 객체를 poll()한다.
- endTimeQueue가 비어있지 않고 endTimeQueue의 peek()값 <= Lecture 객체의 시작 시간이라면 endTimeQueue를 poll()한다.
- endTimeQueue에 Lecture 객체의 종료 시간을 poll()하고 result값을 업데이트한다.

~~하나하나 보면 이해는 가는데 설명을 못하겠네.~~

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.PriorityQueue;
import java.util.Arrays;

public class _1374 {
    private static class Lecture implements Comparable<Lecture> {
        int no, start, end;
        boolean isRemoved = false;

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

        @Override
        public int compareTo(Lecture o) {
            return this.start - o.start;
        }
    }

    public static void main(String [] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // HashMap Key 오름차순 우선순위 정렬
        PriorityQueue<Lecture> pq = new PriorityQueue<>();

        int N = Integer.parseInt(br.readLine());
        for (int i = 0; i < N; i++) {
            String input = br.readLine();

            // StringTokenizer를 사용하여 문자열을 공백으로 분리
            StringTokenizer tokenizer = new StringTokenizer(input);

            // 각 토큰을 정수로 변환
            int lecnum = Integer.parseInt(tokenizer.nextToken());
            int lecstart = Integer.parseInt(tokenizer.nextToken());
            int lecend = Integer.parseInt(tokenizer.nextToken());
            pq.add(new Lecture(lecnum, lecstart, lecend));
        }

        int result = 0;
        PriorityQueue<Integer> endTimeQueue = new PriorityQueue<>();
        while (!pq.isEmpty()) {
            Lecture lecture = pq.poll();
            while (!endTimeQueue.isEmpty() && endTimeQueue.peek() <= lecture.start) {
                endTimeQueue.poll();
            }
            endTimeQueue.offer(lecture.end);
            result = Math.max(result, endTimeQueue.size());
        }
        System.out.println(result);
    }

}

결론

너무 어렵다 ............... 역시 골드는 무리인가...