[알고리즘/ 백준 / Java] 강의실 배정(백준 11000번 문제)

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

11000번: 강의실 배정

 

문제상황

 

처음 이 문제를 접했을때, 저는 강의의 시작(start) 및 끝나는 시간(end)을 담은 Lecture 클래스를 만든 뒤에 입력 값에 따라 LinkedList<Lecture> 리스트에 담았습니다.

그리고 해당 리스트를 강의실 시작시간 기준 오름차순으로 정렬한 뒤,  리스트 내 첫번째 아이템을 기준 값을 정하고 순회하였습니다.

순회 값을 poll 한 뒤 기준 값의 끝나는 시간보다 순회 값의 시작 시간이 크거나 같으면 기준 값을 순회 값으로 바꿔주고, 그렇지 않으면 사전에 미리 만들어둔 임의의 LinkedList에 offer 했습니다.

순회가 끝났다면, 리스트를 미리 만들어둔 임의의 리스트로 바꿔주고 리스트가 비어질때까지 위의 로직을 반복하였습니다.

하지만 아 알고리즘으로는 O(n^2)에 가까운 시간복잡도를 가지기 때문에 시간초과가 났습니다.

 

해결방안

 

이를 해결하기 위한 방법으로 우선순위 큐(PriorityQueue)를 이용하여 새로 해결하였습니다.

방법은 간단히 아래와 같습니다.

1. ArrayList<Lecture> lectures 생성 (Lecture 클래스 : 입력받은 강의 시간 정보를 담은 클래스)
2. lectures를 시작시간(start) 오름차순 기준으로 정렬(같을 경우 끝나는 시간(end) 오름차순)
3. 끝나는 시간의 오름차순 기준의 우선순위 큐(PrirorityQueue) pq 생성
4. lectures를 순회에 앞서 맨 앞의 값을 pq에 offer()
5. 순회하면서 순회 값의 끝나는 시간과 pq.peek() 의 시작시간을 비교해 크거나 같을 경우 poll() 및 offer() 
   반대로 그렇지않는 경우 offer() 만 진행
6. 순회가 끝났다면 pq의 size가 곧 강의실 개수 

public class BaekjoonGreedy11000 {
	
	ArrayList<Lecture> lectures = new ArrayList<>();
	
	public class Lecture implements Comparable<Lecture> {
		
		int start;
		int end;
		
		public Lecture(int start, int end) {
			this.start = start;
			this.end = end;
		}

		@Override
		public int compareTo(Lecture o) {
			if(this.start > o.start) return 1;
			else if(this.start < o.start) return -1;
			else {
				if(this.end > o.end) return 1;
				else if(this.end < o.end) return -1;
			}
			return 0;
		}
		
	}
	
    public void solution() throws Exception {  	
    	input();
    	Collections.sort(lectures);
    	
    	PriorityQueue<Integer> pq = new PriorityQueue<>();
    	
    	for(Lecture l : lectures) {
    		if(pq.isEmpty()) pq.offer(l.end);
    		else {
    			if(pq.peek() <= l.start) {
    				pq.poll();
    				pq.offer(l.end);
    			} else {
    				pq.offer(l.end);
    			}
    		}
    	}
    	
    	System.out.println(pq.size());
    }
    
    public static void main(String[] args) throws Exception {
        new BaekjoonGreedy11000().solution();
    }

    public void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        
        for(int i = 0; i < n; i++) {
        	StringTokenizer st = new StringTokenizer(br.readLine());
        	int start = Integer.parseInt(st.nextToken());
        	int end = Integer.parseInt(st.nextToken());
        	lectures.add(new Lecture(start, end));
        }
    }

}