[백준] 11000번 강의실 배정 - 파이썬(Python)

시간 제한	메모리
1 초	256 MB

 

문제 (링크)

 

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

11000번: 강의실 배정

 

나의 풀이 (Python)

import sys
import heapq
input = sys.stdin.readline

n = int(input())
arr = []

for _ in range(n):
    arr.append(list(map(int, input().split())))

arr.sort()
queue = []
heapq.heappush(queue, arr[0][1])

for i in range(1, n):
    if not queue:
        heapq.heappush(queue, arr[i][1])
    
    else:
        if queue[0] <= arr[i][0]:
            heapq.heappop(queue)
            heapq.heappush(queue, arr[i][1])
        
        else:
            heapq.heappush(queue, arr[i][1])

print(len(queue))

나의 풀이 (Java)

import java.util.*;

public class Main {
	
    static class Lesson implements Comparable<Lesson> {
    	private final int start;
        private final int end;
        
        public Lesson(int start, int end) {
        	this.start = start;
            this.end = end;
        }
        
        public int compareTo(Lesson compare) {
        	if (this.start == compare.start) {
            	return this.end - compare.end;
            }
            
            return this.start - compare.start;
        }
    }
    
    public int solution(List<Lesson> lessons) {
    	Collections.sort(lessons);
		PriorityQueue<Integer> queue = new PriorityQueue<>();
        queue.add(lessons.get(0).end);
        
        for (int i = 1; i < lessons.size(); i++) {
        	if (queue.isEmpty()) {
            	queue.add(lessons.get(i).end);
            }
            
            else {
            	if (queue.peek() <= lessons.get(i).start) {
                	queue.poll();
                    queue.add(lessons.get(i).end);
                }
                
                else {
                	queue.add(lessons.get(i).end);
                }
            }
        }
        
        return queue.size();
    }
    
    
    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        List<Lesson> lessons = new ArrayList<>();
        
        for (int i = 0; i < N; i++) {
        	int start = sc.nextInt();
            int end = sc.nextInt();
            lessons.add(new Lesson(start, end));
        }
    
    	Main main = new Main();
        System.out.println(main.solution(lessons));
    }
}

 

코드 설명 및 풀이법

시간제한이 1초이기 때문에 O(n^2)의 시간복잡도로는 시간초과가 뜬다.

 

큐를 사용해서 문제를 해결할 수 있다.

 

우선, 시작으로 맨 첫 강의가 끝나는 시간을 큐에 넣어준다.

 

그 후, 강의를 하나씩 돌면서 현재 큐에 있는 시간과 강의 시작 시간을 비교해서 시작 시간이 끝나는 시간보다 크거나 같다면, 강의장을 추가할 필요가 없는 것이므로 기존에 들어있던 값을 pop해주고, 새 강의의 끝나는 시각을 업데이트 해준다.

 

만약 다음에 들어오는 강의의 시작시간이 현재 큐에 있는 강의 종료 시각보다 작다면, 새로운 강의장이 필요하다는 의미이므로 그대로 해당 강의의 끝나는 시각을 추가해주면 된다.

 

모든 강의를 돌고 난 후, 큐에 남아있는 원소의 개수가 필요한 강의장의 수가 된다.