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

11000번: 강의실 배정

11000번: 강의실 배정

📄 문제개요

• 강의 시간표가 존재한다. ( 시작시간, 끝나는시간)
• 여러개의 시간표가 주어졌을때, 강의실을 최소화 하는 개수를 구하는 문제이다.
• 수업이 겹치는 강의는 강의실을 다른 강의실에서 강의를 해야한다.

🤔 문제분석

• 강의 시간표를 순회하면서, 우선순위 큐를 사용하여 문제에 접근합니다. 끝나는 시간을 기준으로 큐에 삽입한다.
• 끝나는 시간으로 한 이유 (?) 다음 리터럴에서 시작시간과 끝나는 시간을 단 한번만 확인하면 된다.

📝 의사코드

1. 현재 강의실이 없다면 강의실을 만든다.
2. 강의 시간을 시작 시간을 오름차순으로 순회한다.
3. 현재 강의실 중에서 끝나는 시간이 가장 작은 강의시간을 찾는다. 만약 끝나는 시간이 가장 작은 강의실이 현재 리터럴 에서의 시작시간보다 작을경우, 거기에 강의실을 이어 붙힌다.
4. 만약, 끝나는 시간이 가장 작은 강의실이 없다면 (시작시간이 더 작다면), 이어 붙힐 수 없으므로, 강의실을 만든다.

💻 코드

import sys
import heapq
input = sys.stdin.readline
N = int(input())

course = []
for _ in range(N):
    s, t = map(int, input().split())
    course.append((s, t))

course.sort(key=lambda x:x[0]) # 시작시간으로 정렬한다.

# ? 우선순위 큐를 사용한 이유 : 강의가 끝나는시간이 오름차순으로 정렬되어있을때, 끝나는 시간의 첫번째 인덱스가 s보다 크다면 나머지 뒤에 강의는 볼 필요가 없기때문.
room = []
for s, t in course:
    if room: # 강의실 정보가 존재한다면,
        if s >= room[0]: # 끝나는 시간이 가장 작은시간이 s보다 작을경우 뒤에 수업이 가능하다.
            heapq.heappop(room)
            
        heapq.heappush(room, t)
    else:
        heapq.heappush(room, t)

print(len(room))

🎯 피드백 및 개선사항

• 처음에는 우선순위 큐를 사용하지않고, 강의실을 추가해 가면서, 다른 강의실에 끝나는시간에 일치하는 시간을 찾아서, 그 시간에 끝나는 시간을 자기의 시간으로 바꾸고, 그렇지 않다면 강의실을 추가하는 방식으로 접근하였다. O(n^2) 으로 문제 풀이를 하였습니다.
• 우선순위 큐를 사용하여 끝나는 시간이 가장 작은 순으로 정렬하고, 이미 존재하는 강의실에서 현재 순회하는 강의시간의 시작시간과 끝나는시간을 확인하여, 거기에 이어붙힌다. ( 끝나는 시간이 가장 작기때문에, 그 뒤의 강의실은 볼 필요가 없다. )

❓다른사람은 어떻게 풀었을까?

• 시작시간과, 종료시간을 배열을 나누어서 정렬한뒤, 시작시간을 순회하면서 끝나는시간이 가장 작은 경우부터 순회해, 이어붙힐 수 있다면 이어 붙혀서 문제를 풀이가 존재한다.
• 즉, 시작시간이 끝나는시간보다 클경우( 이어붙 힐 수 없는경우 ) end 의 index를 증가시켜 강의실 개수를 카운팅한다.

import sys

n = int(input())
start = []
end = []

for i in range(n):
    s,e = map(int, sys.stdin.readline().split())
    start.append(s)
    end.append(e)

start.sort()
end.sort()
eindex = 0
freeclass = 0
for i in range(n):
    if start[i]>=end[eindex]:
        freeclass = freeclass+1
        eindex = eindex+1
print(n-freeclass)