백준 1374 - 강의실

문제

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

리뷰

우선순위큐를 통해 풀이할 수 있는 간단한 문제였다.

강의가 연이어서 한 강의실에 강의될 수 있으려면

앞선 강의의 끝나는 시간 <= 뒤이은 강의의 시작 시간

위 조건이 충족되어야 한다. 문제에서는 위 조건에 따라 최소 강의실 수를
도출하는 것을 요구하고 있다.

강의실 수를 최소로 확보하기 위해서 우선 두 가지 우선순위큐를 산정하였다.

• pq : 시작 시간 기준 최소힙
• pq2 : 끝나는 시간 기준 최소힙

강의를 표현하기 위해 번호, 시작 시간, 끝나는 시간을 필드로 가지는 클래스
Class를 정의하고 이를 이용해 정보를 저장했다.

로직은 다음과 같이 전개된다.
1. 우선 들어오는 Class들을 전부 pq에 저장한다.
2. 이후, pq에서 강의를 하나씩 꺼내며 pq2에 저장하는데 이 때,
pq2.peek().end(확인한 강의중 끝나는 시간이 가장 낮은 강의)와
c.start(현재 강의의 시작 시간)을 비교하여

• end <= start인 경우
  강의를 연이어 진행할 수 있으므로 pq2.peek()를 poll()하고 c(현재 강의)를
  pq2에 offer()한다.
• end > start인 경우
  강의를 연이어 진행할 수 없는 경우이므로 강의실 수를 증가시킨다.

로직의 시간복잡도는 $N$개의 강의를 두 개의 우선순위큐를 활용하여 탐색하는 부분에서
$O(NlogN)$으로 수렴하고, 이는 $N=100,000$인 최악의 경우에도 무난히 제한 조건
2초를 통과한다.

코드

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

import static java.lang.Integer.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = parseInt(br.readLine());
        PriorityQueue<Class> pq = new PriorityQueue<>(Comparator.comparingInt(c -> c.start));
        PriorityQueue<Class> pq2 = new PriorityQueue<>(Comparator.comparingInt(c -> c.end));

        int num, start, end;
        StringTokenizer st;
        while (N-- > 0) {
            st = new StringTokenizer(br.readLine());
            num = parseInt(st.nextToken());
            start = parseInt(st.nextToken());
            end = parseInt(st.nextToken());

            pq.offer(new Class(num, start, end));
        }

        int count = 0;
        while (!pq.isEmpty()) {
            Class c = pq.poll();

            if (pq2.isEmpty()) {
                pq2.offer(c);
                count++;
                continue;
            }

            if (pq2.peek().end > c.start) {
                count++;
            } else {
                pq2.poll();
            }

            pq2.offer(c);
        }

        System.out.println(count);
        br.close();
    }

    static class Class {
        int num, start, end;

        public Class(int num, int start, int end) {
            this.num = num;
            this.start = start;
            this.end = end;
        }
    }
}

결과