[그리디] 백준 11000번 강의실 배정 - JAVA

 

오랜만에 알고리즘 풀면서 다양한 난제를 겪었던 문제...ㅋㅋㅎㅎㅋㅋㅎㅎ (해탈)

어린이날 뛰어놀기 전 해당 문제를 기록해보고자 한다.

 

 

---

1. 출처

---

 

11000번: 강의실 배정

 

 

내가 어떠한 코드를 짰고, 왜 실패했는지 기록하겠다.

성공까지 가는 여정 렛츠고...!!

 

 

 

---

2. 설계

---

1) 잘못된 설계 - 시간초과

import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
	static PriorityQueue<Node> pq = new PriorityQueue<>();
	static long[] room;
	static int result;
	static class Node implements Comparable<Node>{
		int start;
		int end;
		
		public Node(int start, int end) {
			super();
			this.start = start;
			this.end = end;
		}

		@Override
		public int compareTo(Node o) {
			if(this.start==o.start) return this.end>o.end?1:-1;
			else return this.start>o.start?1:-1;
		}
		
	}
	
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int count = sc.nextInt();
		
		//초기화
		room = new long[count+1];
		
		for(int i=0;i<count;i++) {
			int start = sc.nextInt();
			int end = sc.nextInt();
			
			pq.add(new Node(start,end));
		}
		
		//입력받기 끝
		
		lectureRoom();
		
		System.out.println(result);
	}
	public static void lectureRoom() {
		while(!pq.isEmpty()) {
			Node cur = pq.poll();
			
			for(int i=0;i<room.length;i++) {
				if(room[i]<=cur.start) {
					//새로운 방
					if(room[i]==0) result++;
					room[i]=cur.end;
					break;
				}
			}
		}
	}
}

강의시간을 모두 우선순위 큐에 넣고, 시작 시간이 빠른순, 시작 시간이 같다면 끝나는 시간이 빠른 순으로 comparable을 이용해 정렬시켰다.

 

room 배열은 현재 0으로 초기화 되어 있으며, 새로운 방이 필요할 때마다 강의가 끝나는 시간으로 수정해줄 것이다.

 

강의 갯수 (강의실의 최대 갯수)만큼 돌면서, 각 강의실에 끝나는 시간과 비교하여 현재 고려하는 강의의 시작시간보다 크거나 같으면 해당 강의실의 끝나는 시점을 바꾸기만 한다. 하지만, 어떤 방에도 들어갈 수 없다면(if(room[i]==0), 새로운 방을 생성하여 그 방에 끝나는 시간을 넣어준다.

 

=> 이 설계를 할 당시에도 20만 개의 데이터가 각자 끝 방에 새롭게 방을 만들면 시간초과가 나겠다고 생각한 설계였으나 역시나... 시간초과가 났다. 한... 84%까지는 정답률로 갔던 것 같다.

 

 

2) 잘못된 설계 - 런타임 에러 (IllegalArgument)

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
	static Node[] lecture;
	static int count;
	static class Node{
		int start;
		int end;
		
		public Node(int start, int end) {
			super();
			this.start = start;
			this.end = end;
		}
		
	}
	
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		count = sc.nextInt();
		
		//초기화
		lecture = new Node[count];
		
		for(int i=0;i<count;i++) {
			int start = sc.nextInt();
			int end = sc.nextInt();
			
			lecture[i]=new Node(start,end);
		}
		
		//강의시작 시간 짧은순, 시작이 같다면 끝이 짧은 순
		Arrays.sort(lecture, new Comparator<Node>() {

			@Override
			public int compare(Node o1, Node o2) {
				if(o1.start==o2.start) return o1.end>o2.end?1:-1;
				else return o1.start>o2.start?1:-1;
			}
		});

		//입력받기 끝
		
		System.out.println(lectureRoom());
	}
	public static int lectureRoom() {
		PriorityQueue<Integer> room = new PriorityQueue<>();
		
		Node first = lecture[0];
		room.add(first.end);
		
		//room에는 끝나는 시간이 가장 작은 순으로 배치되어 있다.
		//가장 작게 끝나는 시간에도 맞출 수 없으면 새롭게 방을 만드는 것이다.
		for(int i=1;i<count;i++) {
			if(room.peek()<=lecture[i].start) {
				room.poll();//기존 방의 끝나는 시간을 수정하기 위해 하나 빼고 수정하여 아래에서 넣는다.
			}
			room.add(lecture[i].end);//if에 걸리지 않았다면 새로운 방이다.
		}
		return room.size();
	}
}

IllegalArgument가 났던 이유는 Comparator에 o1.start>o2.start?1:-1 이었을 때, 만약 두 값이 같다면 어떻게 판단해야 하는가?를 판단하지 못해서... 즉, 모호한 결과값을 마주쳤을 때 어떻게 반환해야할 지 몰라서 도출되었다.

 

그래서 =을 추가해줬더니 바로 정답으로 이어졌다.

 

1번에서 잘못된 설계를 2번에서는 어떻게 고치려고 노력했냐면, room이라는 우선순위 큐를 만들어서 끝나는 시간이 가장 작은 순으로 배치되게 했다.

 

//room에는 끝나는 시간이 가장 작은 순으로 배치되어 있다.
//가장 작게 끝나는 시간에도 맞출 수 없으면 새롭게 방을 만드는 것이다.
for(int i=1;i<count;i++) {
	if(room.peek()<=lecture[i].start) {
		room.poll();//기존 방의 끝나는 시간을 수정하기 위해 하나 빼고 수정하여 아래에서 넣는다.
	}
	room.add(lecture[i].end);//if에 걸리지 않았다면 새로운 방이다.
}

그리고 강의의 시작시간과 현재 room 우선순위큐에 가장 빨리 끝나는 시간을 비교해서 강의의 시작시간이 room의 끝나는 시간보다 크거나 같지 않으면 새로운 방을 만들어주고, 아니라면 해당 room을 뽑아내서 현재 고려하는 강의시간의 끝나는 시간으로 수정해서 다시 넣어줬다.

 

왜냐하면 가장 빨리 끝나는 시간(3)에도 고려하고 있는 강의가 시작시간(만약 2)을 맞춰주지 않으면,

어차피 우선순위큐 room에 뒤로 가봤자 현재 가장 빨리 끝나는 시간(3)보다 느릴 텐데(4) 일일히 강의실의 끝나는 시간을 전부 비교해줄 필요가 없다.

 

 

---

3. 전체 코드

---

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
	static Node[] lecture;
	static int count;
	static class Node{
		int start;
		int end;
		
		public Node(int start, int end) {
			super();
			this.start = start;
			this.end = end;
		}
		
	}
	
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		count = sc.nextInt();
		
		//초기화
		lecture = new Node[count];
		
		for(int i=0;i<count;i++) {
			int start = sc.nextInt();
			int end = sc.nextInt();
			
			lecture[i]=new Node(start,end);
		}
		
		//강의시작 시간 짧은순, 시작이 같다면 끝이 짧은 순
		Arrays.sort(lecture, new Comparator<Node>() {

			@Override
			public int compare(Node o1, Node o2) {
				if(o1.start==o2.start) return o1.end>=o2.end?1:-1;
				else return o1.start>=o2.start?1:-1;
			}
		});

		//입력받기 끝
		
		System.out.println(lectureRoom());
	}
	public static int lectureRoom() {
		PriorityQueue<Integer> room = new PriorityQueue<>();
		
		Node first = lecture[0];
		room.add(first.end);
		
		//room에는 끝나는 시간이 가장 작은 순으로 배치되어 있다.
		//가장 작게 끝나는 시간에도 맞출 수 없으면 새롭게 방을 만드는 것이다.
		for(int i=1;i<count;i++) {
			if(room.peek()<=lecture[i].start) {
				room.poll();//기존 방의 끝나는 시간을 수정하기 위해 하나 빼고 수정하여 아래에서 넣는다.
			}
			room.add(lecture[i].end);//if에 걸리지 않았다면 새로운 방이다.
		}
		return room.size();
	}
}

 

---

 

항상 class에 Comparable만 쓰다가 오랜만에 Arrays.sort를 이용해 Comparator를 썼는데,

안써버릇하니 설계하는데도 한계가 있었던 것 같다.