[자바]백준 11000번 강의실 배정 [그리디][엄탱]

안녕하세요. 개발자 엄탱입니다.
이 글은 알고리즘을 공부하면서 공부 기록용입니다.
그래서 설명마다 일기용으로 편하게 작성하여 반말 형식으로 작성하려고 합니다.
그리고 보시다가 더 좋은 방법이나 잘 못 알고 있는 내용이 있다면 알려주시면 정말 감사하겠습니다.
좋은 하루 되세요 :)

 

그리디 알고리즘이란!?

Greedy는 ‘탐욕스러운, 욕심 많은’ 이란 뜻이다.
탐욕 알고리즘은 말 그대로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다.

 

문제

수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다. 김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다. 

참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.)

수강신청 대충한 게 찔리면, 선생님을 도와드리자!

 

입력

첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000)

이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109)

출력

강의실의 개수를 출력하라.

예제 입력 1

3
1 3
2 4
3 5

예제 출력 1

2

 

알고리즘 분류

• 자료 구조
• 그리디 알고리즘
• 정렬
• 우선순위 큐

 

문제 설명

문제는 수업 스케쥴들 A, B, C가 있다고 가정하고 강의실은 무한대로 있다고 가정하자

이때, 수업 A, B, C를 하기 위해서 강의실을 몇 개가 필요하냐는 것이다.

 

• A가 3시에 끝나고 B가 3시에 시작하고 5시에 끝나고 C가 5시에 시작하는거면 강의실 1개가 필요하다.
• A가 3시에 끝나고 B가 3시에 시작하고 5시에 끝나고 C가 4시에 시작하는거면 강의실 2개가 필요하다.
• A가 3시에 끝나고 B가 2시에 시작하고 5시에 끝나고 C가 4시에 시작하는거면 강의실 3개가 필요하다.

 

해설

이 문제는 그리디 알고리즘 방식으로 하나하나 수업 스케줄을 순서대로 하나하나 해결해나가면 된다.

단, 두가지 정도가 필요하다.

1. 수업 스케줄을 수업 시작시간 기준으로 오름차순 정렬
2. 우선순위큐를 준비하고 우선순위큐의 정렬 기준은 수업 종료시간 기준으로 오름차순 정렬

위 두가지만 준비하면 문제는 쉽게 해결된다.

 

코드

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

public class Main {
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));;
    public static int N;

    public static void main(String[] args) throws Exception {
        N = Integer.parseInt(br.readLine());

        int[][] schedules = initSchedule();

        Arrays.sort(schedules, ((x, y) -> x[0] - y[0]));

        PriorityQueue<int[]> pq = new PriorityQueue<>((x, y) -> x[1] - y[1]);
        pq.offer(schedules[0]);

        for (int i = 1; i < N; i++) {
            int beforeEndTime = pq.peek()[1];
            int nowStartTime = schedules[i][0];

            if (beforeEndTime <= nowStartTime) {
                pq.poll();
            }

            pq.offer(schedules[i]);
        }


        System.out.println(pq.size());
        br.close();
    }

    public static int[][] initSchedule() throws Exception {
        int[][] schedules = new int[N][2];

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            schedules[i][0] = Integer.parseInt(st.nextToken());
            schedules[i][1] = Integer.parseInt(st.nextToken());
        }

        return schedules;
    }
}

 

해설2(생략가능)

이 부분은 코드만 보고 이해되면 넘어가도 상관없다.

 

수업 시작시간 기준으로 오름차순 정렬하는 이유는 아래의 예시와 같은 경우에는 틀리게 되기 때문이다.

1 3

5 7

3 5

 

우선순위큐를 수업 종료시간 기준으로 오름차순 정렬하는 이유는 아래의 예시와 같은 경우에는 틀리게 되기 때문이다.

1 5

2 3

4 7