[99클럽] 백준 1374 강의실

문제 링크

문제

• 각 강의의 시작시간과 종료시간이 주어질 때, 최소한으로 필요한 강의실의 개수를 구하여라
  • 하나의 강의실에서 동시에 2개 이상의 강의를 진행할 수 없다.
  • 강의 종료 시간과 또 다른 강의의 시작 시간이 동일할 때에는 하나의 강의실을 이어서 사용할 수 있다.

최종 코드

import java.util.PriorityQueue;

public class Main {
	public static void main(String[] args) throws Exception {
		int N = read();
		PriorityQueue<int[]> classes = new  PriorityQueue<>((int[] o1, int[] o2) -> {
			if (o1[0] == o2[0]) return o1[1] - o2[1];
			return o1[0] - o2[0];
		});
		
		PriorityQueue<Integer> ends = new  PriorityQueue<>();
		
		for (int i = 0; i < N; i++) {
			int classNo = read();
			int startTime = read();
			int endTime = read();
			classes.add(new int[] {startTime, endTime});
		}
		
		int room = 0;
		while (!classes.isEmpty()) {
			int[] now = classes.poll();
			
			if (ends.isEmpty()) {
				room++;
				ends.add(now[1]);
				continue;
			} 
			
			int preEnd = ends.peek();
			if (now[0] < preEnd) {
				room++;
				ends.add(now[1]);
			}
			else {
				ends.poll();
				ends.add(now[1]);
			}
		}
		
		System.out.println(room);
		
	}
	
	private static int read() throws Exception {
		int c, n = System.in.read() & 15;
		while ((c = System.in.read()) > 32)
			n = (n << 3) + (n << 1) + (c & 15);
		return n;
	}
}

배운점

우선순위 큐(최소힙)

PQ는 2개를 사용했다.

• 강의 정보
  • 시작-종료 시간을 배열로 저장하고,
  • 시작 시간이 빠른 것부터 꺼내어(poll) 처리한다.
• 강의 종료 시간
• 이미 배치한 강의의 종료 시간을 저장하고
• 종료 시간이 빠른 것부터 확인(peek)하여 배치가 필요한 강의 시작 시간과 비교한다.
• 비교 결과에 따라 새로운 강의를 배치(add만)하거나 덮어쓴다(poll -> add).

그리디 알고리즘 익숙해지기

최적의 선택 : 강의 시작 시간이 바로 직전 강의 종료 시간보다 이전(미만)일 때에는 강의실을 추가하고, 아닐 경우에는 기존 강의실을 사용한다.

1. 강의 정렬
   강의실 배치에서 가장 빠른 시작 시간의 강의를 우선적으로 처리해야 한다.
   우선순위 큐에 int[]을 넣어서 사용하기 때문에, 별도로 Comparator의 정렬 기준을 재정의 해준다.

	PriorityQueue<int[]> classes = new  PriorityQueue<>((int[] o1, int[] o2) -> {
		if (o1[0] == o2[0]) return o1[1] - o2[1];
		return o1[0] - o2[0];
	});

2. 우선순위 큐를 이용한 강의실 관리
   ends 큐로 현재 진행 중인 강의의 종료 시간을 관리한다.
   현재 강의의 시작 시간이 ends 큐에 있는 peek 값(가장 빨리 끝나는 시간)보다 작다면, 새로운 강의실을 추가해야 하므로 room++로 강의실 수를 증가시킨다.

	int preEnd = ends.peek();
		if (now[0] < preEnd) {
			room++;
			ends.add(now[1]);
		}

그렇지 않다면, 기존 강의실을 재사용 가능하므로 ends.poll()을 호출하여 기존 강의실의 종료 시간을 제거하고, 현재 강의의 종료 시간을 ends 큐에 추가한다.

	else {
		ends.poll();
		ends.add(now[1]);
	}

3. 결과
   room을 출력한다. ends 큐의 크기가 항상 현재 필요한 강의실 수가 되기 때문에 ends의 크기를 출력해도 된다.

Kotlin code

import java.io.StreamTokenizer
import java.util.PriorityQueue

fun main() = with(StreamTokenizer(System.`in`.bufferedReader())) {
    fun read() : Int {
        nextToken()
        return nval.toInt()
    }

    val N = read()
    val classes = PriorityQueue<IntArray> { o1, o2->
        if (o1[0] == o2[0]) return@PriorityQueue o1[1] - o2[1]
        return@PriorityQueue o1[0] - o2[0]
    }

    repeat(N) {
        val no = read()
        val s = read()
        val e = read()
        classes.add(intArrayOf(s, e))
    }

    val ends = PriorityQueue<Int>()

    while (classes.isNotEmpty()) {
        val now = classes.poll()

        if (ends.isEmpty()) {
            ends.add(now[1])
            continue
        }

        val preEnd = ends.peek()
        if (now[0] < preEnd) {
            ends.add(now[1])
        }
        else {
            ends.poll()
            ends.add(now[1])
        }
    }

    println(ends.size)
}