[백준] 19598 최소 회의실 개수 - 그리디 + 우선순위큐(PriorityQueue) JAVA

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

19598번: 최소 회의실 개수

코드설명

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

 

이 문제의 핵심은 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 이렇게 자동으로 가장 작은 값이 우선순위가 가장 높게 되어 나옵니다.

(처음에 Node로 PriorityQueue를 사용하였다가, CompareTo가 적용되어 잘못 정렬되었습니다.)

코드

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


public class Main {
	
	public static int N,K;
	public static Node[] node;
	public static int answer =0 ;
    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 startTime = Integer.parseInt(st.nextToken());
    		int endTime =Integer.parseInt(st.nextToken());
    		node[i] = new Node(startTime, endTime); 
    	}
    	
    	Arrays.sort(node);
    	
    	PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
    	pq.offer(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;
//		}
//	}
	
}