[알고리즘] 백준 11000 강의실 배정 Java

문제 정보

플랫폼 : 백준
분류 : 그리디 알고리즘
난이도 : 골드5
링크 : https://www.acmicpc.net/problem/11000

입력 데이터와 시간제한 검증

입력 데이터 갯수 : 20만 > BufferedReader
O(nlogn) 풀이 (정렬, 우선순위큐): 시간제한 ok
자료형 : 최대 1억 > int사용

풀이

처음에 풀었을 때 시간초과가 났다. Time {int start, int end}클래스를 만들어서, InputData를 ArrayList<Time>에 넣었다. 이후에 start를 오름차순 (start가 같으면 end로 오름차순)정렬 해주고, 리스트를 순차적으로 돌면서 현재 리스트를 remove하고, 현재 end보다 큰 가장 가까운 값을 이분탐색으로 찾아내는 방식을 사용했다.

이분탐색의 시간복잡도가 O(logn)이므로 충분할거라고 생각했지만, 문제는 ArrayList의 연산에 있었다. ArrayList의 get 메소드는 O(1)이지만, add, remove에 대해서는 O(n)이기 때문에 O(n^2)풀이가 돼서 85%에서 시간초과가 났다. 이후 우선순위 큐(PriorityQueue)로 풀이방식을 바꿨다. 우선순위 큐의 시간복잡도는 O(logn)이기 때문에, 시간초과가 나지 않는다. (우선순위 큐는 최대힙/최소힙 자료구조를 사용한다.)

1. Input Data를 2차원 배열로 받는다. (new int[n][2])
2. 입력 데이터를 오름차순으로 정렬해준다. (시작 시간이 같다면, 끝나는 시간을 오름차순으로 정렬)
3. PriorityQueue(우선순위 큐)를 만들어주고, (정렬된)배열의 첫 번째 end값을 큐에 넣는다.
4. 배열을 두 번째 값부터 순회하면서, start가 PriorityQueue의 peek()보다 작거나 같다면, pq에서 하나 뺀다.
4-1. 순회하면서, 현재 end값을 새로 pq에 넣어준다.
5. pq에 남아있는 데이터의 갯수가 필요한 강의실의 갯수이다.

예시 데이터로 확인해보자. InputData는 다음과 같다.

5
1 4
5 7
4 5
2 5
3 8

먼저, 정답은 3이고 아래 테이블과 같이 배정하면 된다.

1) 입력 데이터를 오름차순으로 정렬해보자.

1 4
2 5
3 8
4 5
5 7

2) 첫 번째 데이터의 end값 (4)를 pq에 넣는다.
3) 두 번째 데이터의 start값 (2)를 pq.peek() (4)와 비교한다. pq.peek()이 더 크므로, pq.poll()을 수행하지 않고 end값을 add한다. (현재 pq : 4, 5)이는, 가장 빨리 끝나는 강의의 end와 이어지지 않고, 새로운 강의실의 배정이 필요함을 의미한다.
＊가장 빨리 끝나는 강의인 이유는, PriorityQueue이기 때문.

4) 세 번째 데이터의 start값 (3)을 pq.peek() (4)와 비교한다. 3번과 마찬가지로 poll()을 수행하지 않고 add한다. (현재 pq : 4, 5, 8)
5) 네 번째 데이터의 start값 (4)을 pq.peek() (4)와 비교한다. pq.peek() <= start값 이므로, poll()을 수행하고, end값을 add한다. poll()을 수행한다는 것은, 이전 강의실에 이어서 진행할 수 있음을 의미한다. end값을 add한다는 것은, 해당 강의실에 끝나는 시간이 갱신됨을 의미한다. (현재 pq : 5, 5, 8)

6) 다섯 번째 데이터의 start값 (5)를 pq.peek() (5)와 비교한다. 위 5번과 마찬가지로 poll() 수행 후, end값을 add한다. (사진에서는 강의실 1에 붙였지만, 강의실 2에 붙을 수도 있다.)

최종적으로 pq에는 각 강의실마다 끝나는 시간 (5, 7, 8)이 남아있게 되며, 이는 강의실의 갯수와 동일하다.

2차원 배열의 정렬과 PriorityQueue를 사용했기 때문에 시작하는 시간별로 가장 빨리 끝나는 강의에 이어붙일 수 있는지 검사가 가능하다.

코드

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = stoi(br.readLine());
		
		//1. Input Data를 2차원 배열로 받는다. (new int[n][2])
		int[][] arr = new int[n][2];
		for(int i = 0; i < n; i++) {
			String[] input = br.readLine().split(" ");	
			arr[i][0] = stoi(input[0]);
			arr[i][1] = stoi(input[1]);
		}

		//2. 입력 데이터를 오름차순으로 정렬해준다. (시작 시간이 같다면, 끝나는 시간을 오름차순으로 정렬)
		Arrays.sort(arr, new Comparator<int[]>() {
			public int compare(int[] o1, int[] o2) {
				if(o1[0] == o2[0]) return o1[1] - o2[1];
				return o1[0] - o2[0];
			}
		});
		//3. PriorityQueue(우선순위 큐)를 만들어주고, (정렬된)배열의 첫 번째 end값을 큐에 넣는다.
		PriorityQueue<Integer> pq = new PriorityQueue<>();
		pq.add(arr[0][1]);
		
		//4. 배열을 두 번째 값부터 순회하면서,
		for(int i = 1; i < n; i++) {
			//start가 PriorityQueue의 peek()보다 작거나 같다면, pq에서 하나 뺀다.
			if(pq.peek() <= arr[i][0]) pq.poll();
			
			//4-1. 순회하면서, 현재 end값을 새로 pq에 넣어준다.
			pq.add(arr[i][1]);
		}
		
		//5. pq에 남아있는 데이터의 갯수가 필요한 강의실의 갯수이다.
		System.out.println(pq.size());
		br.close();
	}
	public static int stoi(String str) {return Integer.parseInt(str);}
}

더 많은 정답 코드

블로그를 쓰기 이전에 풀어본 문제들이 많다. 해설강의는 없지만, 백준 문제의 풀이 코드가 필요한 경우 이곳을 클릭하여 소스코드를 참조해보도록 하자. 단, 코드만 복사-붙여넣기 하는것은 본인에게 결코 도움이 되지 않는다. 반드시 먼저 생각해보고, 막히는 경우에 참고하고 왜 이렇게 코드가 작성됐는지를 다시 한 번 생각해보는 습관을 들이자.