11000번 문제

문제

풀이

첫번째 풀이

접근 방식

1. 강의를 종료 시간이 더 빠른 순으로 정렬한다. (정렬된 강의를 뒤쪽으로만 순회할 때 현재 강의보다 먼저 종료되는 강의가 없도록 하기 위함.)
2. 정렬된 강의를 순회한다. 이 때 시작 시간이 현재 강의의 종료 시간과 같거나 이후인 것을 찾으면 삭제하고, 종료 시각을 업데이트한다. (같은 강의실을 사용하는 것으로 간주.)

즉, 현재 강의의 종료 시간을 기준으로 다른 강의들의 시작 시간을 비교한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st;
        LinkedList<int[]> classList = new LinkedList<>();
        for(int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            classList.add(
                new int[] {Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken())}
            );
        }
        Collections.sort(classList,(c1,c2) -> {
            return c1[1]-c2[1]; // 끝나는 시각이 더 빠른 것 우선으로 정렬
        });

        int cnt = 0;
        while (!classList.isEmpty()) {
            cnt++;
            int end = classList.get(0)[1];
            classList.remove(0);
            for(int i=0; i<classList.size();) {
                if(classList.get(i)[0] >= end) {
                    end = classList.get(i)[1];
                    classList.remove(i);
                } else {
                    i++;
                }
            }    
        }
        System.out.println(cnt);
    }
}

그 결과는?

ㅎㅎ 다른 방법을 찾아야 한다.
위 풀이는 결국 각 강의마다 뒤에 존재하는 모든 강의를 비교한다.
따라서 최악의 경우 O(N^2)의 시간복잡도를 가진다.

두번째 풀이

1. 강의를 시작 시간이 빠른 순으로, 시작 시간이 같으면 종료 시간이 빠른 순으로 정렬한다.
2. 정렬된 강의들을 순회한다. 이 때 순회한 강의들의 종료 시간을 또 다른 자료구조에 저장한다.
3. 이전에 순회한 강의 중 현재 강의의 시작 시간보다 이전에 종료된 강의가 있는 지 확인한다.
   3-1. 있다면 같은 강의실에서 강의를 진행하는 것으로 간주한다. (기존 종료 시간을 현재 종료 시간으로 업데이트)
   3-2. 없다면 새 강의실에서 현재 강의를 진행한다. (현재 종료 시간을 추가)

즉, 현재 강의의 시작시간을 기준으로 이전에 종료된 강의를 찾는 것이다.
이미 순회한 강의 중, 종료 시간이 빠른 순으로 저장되는 자료구조를 사용함으로써 현재 강의의 시작 시간보다 이전에 종료된 강의가 있는 지 확인하는 과정을 O(1)의 시간만에 수행할 수 있다.

현재 강의의 시작 시간 < 가장 빠른 종료 시간 이라면, 이미 순회한 강의들은 모두 현재 강의의 시작 시간보다 뒤에 종료된다는 의미이므로 다른 강의들을 비교할 필요가 없음

제출 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st;
        LinkedList<int[]> classList = new LinkedList<>();
        for(int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            classList.add(
                new int[] {Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken())}
            );
        }
        Collections.sort(classList,(c1,c2) -> {
            if(c1[0]!=c2[0]) {
                return c1[0]-c2[0]; // 시작 시간이 빠른 순으로 정렬
            } else {    
                return c1[1]-c2[1]; // 시작 시간이 같다면 종료 시간이 빠른 순으로 정렬
            }
        });

        PriorityQueue<Integer> roomQ = new PriorityQueue<>(); 
        // 필요한 강의실. 해당 강의실에서 수업하는 강의가 마지막으로 끝나는 시간이 저장됨.
        int startTime = 0;
        int endTime = 0;
        for(int[] classInfo : classList) {
            startTime = classInfo[0];
            endTime = classInfo[1];
            if(!roomQ.isEmpty() && roomQ.peek() <= startTime) { 
                roomQ.poll(); // 현재 강의를 이 강의실에서 수행함을 의미, 업데이트를 위해 빼줌
            }
            roomQ.add(endTime); // 현재 강의가 끝나는 시간으로 업데이트 Or 강의실 추가
        }
        System.out.println(roomQ.size());
    }
}

---