[자바] 백준 11000번: 강의실 배정

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

11000번: 강의실 배정

 

---

프로그램 동작 설명

수업시간이 가장 많이 겹칠 때, 겹치는 수업의 개수가 몇 개인가?

저번에 풀었던 문제처럼~ 뭔가 스택이나 큐같은걸 써야하나 곰곰이 생각해봤는데

우선순위 큐를 사용하는게 좋을 것 같았다.

 

각각의 수업을 Job이라는 클래스를 이용해서 표현하려 했다.

멤버변수로 수업의 시작시간, 끝나는시간인 start - end가 있다.

 

우선순위 큐는 Job들을 담을 건데,

job의 end(수업의 끝나는시간)을 기준으로, 가장 작은게 head에 오게 설정했다.

.

.

 

우선 N개의 수업들을 시작시간 기준으로 오름차순 정렬한다.

정렬해놓은 수업 리스트를 하나씩 순회하는데,

1. 우선순위큐가 비었거나 || 큐의 head의 end(수업 끝나는시간)보다 현재 수업의 start(수업 시작시간)가 더 작은 경우

 이 경우는 앞선 수업들이 끝나지 않아, 현재 수업만 추가되면 되는 경우다.

 

2. 1번의 else

 이 경우는 앞선 수업들 중 끝난 수업이 존재하는 경우이다.

 이 때는 끝난 수업들을 모두 큐에서 pop해준다.

 그 이후에 현재 수업을 큐에 add한다.

 

---

코드

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

public class P11000 {

	static class Job implements Comparable<Job>{
		int start;
		int end;
		public Job(int start, int end) {
			this.start=start;
			this.end=end;
		}
		@Override
		public int compareTo(Job job) {
			if(this.end > job.end) {
				return 1;
			}
			else if(this.end < job.end) {
				return -1;
			}
			return 0;
		}
	}
	
	public static void main(String[] args) throws NumberFormatException, IOException {

		PriorityQueue<Job> pq=new PriorityQueue<>();
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		

		int count=0;
		int maxCount=0;
		int n=Integer.parseInt(br.readLine());
		
		int[][] array=new int[n][2];
		
		for(int i=0;i<n;i++) {
			st=new StringTokenizer(br.readLine());
			int start=Integer.parseInt(st.nextToken());
			int end=Integer.parseInt(st.nextToken());
			array[i][0]=start;
			array[i][1]=end;
		}

		Arrays.sort(array, new Comparator<int[]>() {
			    @Override
				public int compare(int[] o1, int[] o2) {
			    	 if(o1[0] == o2[0]) {
		                	 return o1[1] - o2[1];
			    	 }else {
			    		 return o1[0] - o2[0]; 
			    	 }
		           }
		        });
		
		
		for(int i=0;i<n;i++) {
			//st=new StringTokenizer(br.readLine());
			//int start=Integer.parseInt(st.nextToken());
			//int end=Integer.parseInt(st.nextToken());
			int start=array[i][0];
			int end=array[i][1];
			if(pq.peek()==null || pq.peek().end > start) {//큐가 비었거나 앞 작업이 안끝남
				count++;
				if(maxCount<count)
					maxCount=count;
				pq.add(new Job(start,end));
			}
			else {//큐가 비지않고 앞작업 중 끝난게 있음
				while(!pq.isEmpty()&&pq.peek().end <=start) {
					pq.remove();
					count--;
					
				}
				pq.add(new Job(start,end));
				count++;
			}
		}
		System.out.println(maxCount);
	}

}

(자바가 익숙치 않아 몇몇군데에서 애먹었다.)

 

지금 다시 이 코드를 보니 문제점이 꽤나 많다

이미 시작한 수업은 시작시간을 두번다시 사용하지 않는다.

그렇다면 애초부터 큐에 시작시간을 넣지 않아도 되고(수업의 끝나는시간만 기입) -> Job클래스도 없었어도 됐을 것 같다.

 

---

새로 배운 부분

 

- PriorityQueue 에서 내가 만든 클래스를 사용하기 위해 implements Comparable 한 것

static class Job implements Comparable<Job>{
		int start;
		int end;
		public Job(int start, int end) {
			this.start=start;
			this.end=end;
		}
		@Override
		public int compareTo(Job job) {
			if(this.end > job.end) {
				return 1;
			}
			else if(this.end < job.end) {
				return -1;
			}
			return 0;
		}
	}

priorityQueue가 내가 만든 클래스인 Job을 담기 때문에, 비교하는 기준을 세워야 한다.

 

Job implements Comparable<Job>

해서 Comparable을 구현해주었다.

 

 

- 이차원 배열에서 1열을 기준으로 오름차순 정렬하기 위해 Arrays.sort메소드 사용한 것

Arrays.sort(array, new Comparator<int[]>() {
			    @Override
				public int compare(int[] o1, int[] o2) {
			    	 if(o1[0] == o2[0]) {
		                	 return o1[1] - o2[1];
			    	 }else {
			    		 return o1[0] - o2[0]; 
			    	 }
		           }
		        });

Comparator 익명 클래스로 사용해서 오버라이딩 함.