[백준] 11000 강의실 배정 - 그리디 + 우선순위큐(PriorityQueue) JAVA

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

11000번: 강의실 배정

코드설명

그리디 알고리즘과 우선순위큐를 활용하여 해결할 수 있습니다.

 

이 문제의 핵심은 PQ의 SIZE가 곧 강의실의 개수라는것을 이해해야합니다.

 

문제예시

3
1 3
2 4
3 5

위의 문제예시의 로직을 설명해보겠습니다.

먼저 정렬합니다. (시작순서 오름차순, 종료순서 오름차순)

그러면

1 3

2 4

3 5 

와 같습니다.

 

먼저 가장 첫번째의 Node[0].endTime으로써 PriorityQueue에 3 이 들어갑니다.

이제 PQ가 값이 없을때까지 돌면서,

처음에는 endTime이 3이 들어갔으니 이제는 startTime으로 비교합니다.

pq.peek()으로 endTime을 가져오고, 다음 시간표인 Node[1].startTime과 비교하였을때

pq에 존재하는 endTime이 <= 인 경우라면, 해당 강의시간 다음에 바로 다음강의를 넣을 수 있습니다.

그렇지만, Node[1].startTime은 2 입니다. 그러므로, pq.poll()을 하지않고, 다른 강의실에 넣는다는 개념으로 냅둡니다.

즉, PQ에서의 개수는 곧 강의실의 개수입니다.

 

1. 시작순서 오름차순, 종료순서 오름차순으로 Arrays.sort 합니다.

이때, Arrays.sort를 정확하게 하지않으면 RuntimeException이 나옵니다.

 

2. PriorityQueue<Integer>로 사용해야합니다.우선순위큐는 기본적으로 우선순위가 가장 높은 값이 먼저 나옵니다. 기본 Integer를 사용할시 숫자가 작을수록 우선순위가 높습니다. 즉, 여기서는 endTime이 가장 작은 순서대로 나옵니다.

이렇게 처리해야만, 강의실을 배분할 수 있습니다.

만약 Node로 넣는다면, Node의 compareTo가 적용되어 우선순위큐의 순서가 뒤바뀝니다.

Integer 형태를 사용하여 PriorityQueue를 사용하면,  10 20 50 30 40 이 들어가면, 10 20 30 40 50 이렇게 자동으로 가장 작은 값이 우선순위가 가장 높게 되어 나옵니다.

//	@Override
//	public int compareTo(Node other) {
//		if(this.startTime == other.startTime)
//			return this.endTime - other.endTime;
//		return this.startTime - other.startTime;
//	}
	
	@Override
	public int compareTo(Node other) {
		if(this.startTime > other.startTime) {
			return 1;
		}else if(this.startTime == other.startTime) {
			if(this.endTime > other.endTime) {
				return 1;
			}else if(this.endTime == other.endTime){
				return 0;
			}else {
				return -1;
			}
		}else {
			return -1;
		}
	}

 

2. 

코드

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


public class Main {
	
	public static int N;
	public static int answer = 1;
	public static Node[] node;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	N = Integer.parseInt(st.nextToken());
    	node = new Node[N];
    	
    	for(int i=0;i<N;i++) {    		
    		st = new StringTokenizer(br.readLine());
    		int a = Integer.parseInt(st.nextToken());
    		int b = Integer.parseInt(st.nextToken());
    		node[i] = new Node(a, b);
    	}
    	
    	//시작시간을 기준으로 오름차순으로 정렬하면서, 
    	//시작시간이 같다면, 종료시간을 기준으로 오름차순 정렬합니다.
    	Arrays.sort(node);

    	
    	//우선순위 큐에는 종료시간만 들어가며, 오름차순으로 자동 정렬됩니다.
    	PriorityQueue<Integer> pq = new PriorityQueue<>();
    	pq.add(node[0].endTime);

    	for(int i=1;i<N;i++) {
    		//우선순위 큐에서 종료시간과 현재 강의시간의 시작시간을 비교하여
    		//종료시간이 다음 강의시간보다 더 작거나 같다면, 
    		if(pq.peek() <= node[i].startTime) {
    			pq.poll(); //해당 강의를 종료처리한다.
    		}
    		pq.add(node[i].endTime);
    	}
    	System.out.println(pq.size());
    }
}

class Node implements Comparable<Node>{
	int startTime;
	int endTime;
	public Node(int startTime, int endTime) {
		this.startTime = startTime;
		this.endTime = endTime;
	}

//	@Override
//	public int compareTo(Node other) {
//		if(this.startTime == other.startTime)
//			return this.endTime - other.endTime;
//		return this.startTime - other.startTime;
//	}
	
	@Override
	public int compareTo(Node other) {
		if(this.startTime > other.startTime) {
			return 1;
		}else if(this.startTime == other.startTime) {
			if(this.endTime > other.endTime) {
				return 1;
			}else if(this.endTime == other.endTime){
				return 0;
			}else {
				return -1;
			}
		}else {
			return -1;
		}
	}
}