강의실 배정

알고리즘 구분 : 그리디

최초 문제 풀이 : 처음 접근한 풀이법은 입력받은 값을 시작시간대 기준으로 정렬한 이후, 강의실 별로 시간표를 채워가는 방식이였습니다. 즉 강의실 하나를 채우고, 입력한 데이터 값을 한 번 순회하였다면, 다른 새 강의실의 시간표를 남은 데이터 값 중에서 채우는 방식으로 소스 코드였습니다. 그러나, 해당 코드는 시간초과 판정을 받았습니다.

시간 초과 소스 코드 :

# 강의실 배정
n = int(input())

# 값 입력
data = []
for _ in range(n):
    data.append(list(map(int, input().split())))
data.sort()

# end : 종료 시각 / temp : 임시 저장 리스트
# room_cnt : 사용하는 강의실 수 체크 / room = 현재 사용하고 있는 시간대
end = 0
room_cnt = 0
room = []
temp = []

# data 확인 
while len(data) > 0:
    end = data[0][1]
    room.append(data[0])

    for i in range(1, len(data)):
        if data[i][0] >= end:
            room.append(data[i])
            end = data[i][1]
        else:
            temp.append(data[i])

    # 한 강의실 사용시간표 확정 및 새로운 강의실 시간표 짜기
    data = temp
    temp = []
    end = 0
    room_cnt += 1
    room = []
    
print(room_cnt)

정답 문제 풀이 : 시간 초과를 해결하여야 하므로, 시간 초과를 해결할 수 있는 O(logn)의 시간 복잡도를 가지고 있는 우선순위 큐를 이용했습니다. 강의 시간을 정렬 후 강의의 끝나는 시간을 다른 강의의 시작 시간과 비교하여, 시작 시간이 크거나 같다면 같은 강의실에서 강의가 가능하다는 의미이므로 원래 존재하던 강의를 삭제하고 시작 시간이 조건에 부합하는 강의를 큐에 삽입합니다. 반대로, 강의를 할 수 없다면, 기존 상의를 삭제하지 않은 상태에서 시작 강의를 새롭게 큐에 삽입하여 다른 강의실을 사용해야 한다는 것을 표현했습니다.

정답 소스 코드 :

# 강의실 배정
import sys
import heapq

n = int(sys.stdin.readline())

# 값 입력
data = []
for _ in range(n):
    data.append(list(map(int, sys.stdin.readline().split())))
data.sort(key = lambda x: x[0])

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

for i in range(1, n):
    if queue[0] > data[i][0]:
        heapq.heappush(queue, data[i][1])
    else:
        heapq.heappop(queue)
        heapq.heappush(queue, data[i][1])

print(len(queue))

• 문제 출처 : https://www.acmicpc.net/problem/11000
• 해당 정답 소스 코드는 백준에서 "맞았습니다!!" 판정을 받았습니다.