1374_강의실

사용 알고리즘: 그리디 + "우선순위 큐"

사용 언어: java

 

처음에 시간 초과가 난 코드

package week10;

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

public class Main_bj_1374_강의실 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt(); //강의 수
		int[][] arr = new int[n][3];
		
		for (int i = 0; i < arr.length; i++) {
			arr[i][0] = sc.nextInt(); //강의 번호
			arr[i][1] = sc.nextInt(); //강의 시작 시간
			arr[i][2] = sc.nextInt(); //강의 종료 시간
		}
		
		Arrays.sort(arr, (o1, o2) -> {
			if(o1[1] != o2[1]) return o1[1] - o2[1];
			else return o1[2] - o2[2];
		});
//		for(int i=0; i<n; i++) System.out.println(Arrays.toString(arr[i]));
		
		System.out.println(classRoom(n, arr));
	}

	private static int classRoom(int n, int[][] arr) {
		List<Integer> rooms = new ArrayList<>(); //Integer: 강의 끝나는 시간
		
		rooms.add(arr[0][2]); //처음 강의는 집어넣고 시작~
		int cl = 1; //시작한 강의 수
		
		while(cl < n) {
			int startTime = arr[cl][1]; //시작 시간 (list와 비교)
			int endTime = arr[cl++][2]; //끝나는 시간 (list업데이트)
			
			rooms = setRooms(rooms, startTime, endTime);
		}
		
		return rooms.size();
	}

	private static List<Integer> setRooms(List<Integer> rooms, int startTime, int endTime) {
		Collections.sort(rooms); //강의가 빨리 끝나는 순으로 정렬
		
		int earliestEndingLecture = rooms.get(0);
		
		if(earliestEndingLecture <= startTime) { //startTime 전에 빈 강의실이 생기면 그대로 사용
			rooms.set(0, endTime);
		} else { //빈 강의실이 없다면, 강의실 하나 더 만들기
			rooms.add(endTime);			
		}
		
		return rooms;
	}

}

 

 

정답 코드

package week10;

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

public class Main_bj_1374_강의실 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt(); //강의 수
		int[][] arr = new int[n][3];
		
		for (int i = 0; i < arr.length; i++) {
			arr[i][0] = sc.nextInt(); //강의 번호
			arr[i][1] = sc.nextInt(); //강의 시작 시간
			arr[i][2] = sc.nextInt(); //강의 종료 시간
		}
		
		Arrays.sort(arr, (o1, o2) -> {
			if(o1[1] != o2[1]) return o1[1] - o2[1];
			else return o1[2] - o2[2];
		});
//		for(int i=0; i<n; i++) System.out.println(Arrays.toString(arr[i]));
		
		System.out.println(classRoom(n, arr));
	}

	private static int classRoom(int n, int[][] arr) {
		PriorityQueue<Integer> pq = new PriorityQueue<>((o1, o2) -> o1 - o2); //빨리 끝나는 순으로 정렬
		
		int cnt = 1; //처음 시작하는 강의는 무조건 교실 하나 배정
		pq.add(arr[0][2]);
		
		for (int room = 1; room < n; room++) {
			int startTime = arr[room][1];
			int endTime = arr[room][2];
			
			//모든 강의실이 다 비어있을 때
			if(pq.isEmpty()) {
				pq.add(endTime);
				continue;
			}
			
			if(pq.peek() > startTime) { //빈 강의실x -> 강의실 하나 더 배정
				cnt++;
			} else { //빈 강의실 만들기
				pq.poll();
			}
			pq.add(endTime); //지금 시작한 수업 pq에 넣기
		}
		
		return cnt;
	}

}

 

 

고찰:

시간 초과가 난 코드와, 정답 코드의 논리는 크게 다를 게 없다.

다만 첫 코드는 우선순위 큐 대신, List만을 가지고 계속 sorting을 해주었다.

 

gpt검색 결과 Collections.sort()와 PriorityQueue 둘 다 시간 복잡도는 O(n log n)이라고 한다.

 

첫 코드를 개선하기 위해 강의실이 빠졌을 때만 sorting을 하게 고친 코드도 있지만, 역시 시간 초과가 났다.

 

결국 n log n의 정렬을 몇 번 수행하느냐가 문제의 핵심이었던 거 같다.

 

 

접근은 거의 다 해놓고 왜 이런 데서 자꾸 아쉬운지... 참...