백준(G5) 11000번: 강의실 배정(파이썬, Python3)

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

11000번: 강의실 배정

이 문제는 골드 치고는 생각보다 쉬웠던 문제 같다..!

우선 그리디 알고리즘과 우선순위 큐 문제를 자주 푸셨던 분은 쉽게 푸실 수 있는 문제다.

그리디 알고리즘은 추후에 정리해서 올리도록 하겠다.

우선순위 큐 문제는 밑에 링크를 보고 오시면 이해가 쉽게 됩니다.

https://solution-is-here.tistory.com/114

백준(S2) 11279번: 최대 힙(파이썬, Python3)및 heapq 설명

 

힙 알고리즘을 완벽히 이해한 것으로 가정하고 설명하겠습니다.

문제를 보면 전형적인 그리디 알고리즘 문제인 것을 알수가 있다.

수업이 끝나는 시간보다 다음 수업이 시작하는 시간이 빠르면 강의실을 하나 늘리고 시작하는 시간이 더 느리면 강의실을 늘리지 않고 같은 강의실에서 다음 수업까지 한다고 이해하시면 됩니다.

 

그러긴 위해서는 수업을 정렬 시키고 if 조건문을 사용해서 끝나는 시간과 시작하는 시간을 비교하면 됩니다.

코드와 함께 설명하겠습니다.

q = []
num = int(input())
for i in range(num):
    q.append(list(map(int,input().split())))
q.sort()

q라는 리스트를 만든 뒤, 입력받은 수들을 리스트의 형태로 q에 넣었습니다.

그리고 sort함수를 사용해서 입력받은 수들을 오름차순으로 정렬시켰습니다.

 

 

nums_of_classroom = []
heapq.heappush(nums_of_classroom,q[0][1])
for i in range(1,num):
    if nums_of_classroom[0] > q[i][0]:
        heapq.heappush(nums_of_classroom,q[i][1])
    else:
        heapq.heappop(nums_of_classroom)
        heapq.heappush(nums_of_classroom,q[i][1])

강의실의 개수를 파악하는 nums_of_classroom이라는 리스트를 만든 뒤, q 리스트에 있는 첫 번째 수업이 끝나는 시간을 heappush함수를 사용해서 넣었습니다.

그 후, 1부터 num까지 반복되는 반복문을 이용해서 nums_of_classroom에 있는 숫자(수업이 끝나는 시간)과 q[i][0](i -1번째 수업이 시작하는 시간)을 비교해서 수업이 끝나는 시간이 더 크면 강의실의 개수를 파악하는 리스트에 heappush 함수를 사용해서 숫자를 넣었습니다.

만약 수업 끝나는 시간이 더 작다면 heappop을 사용해 가장 작은 숫자를 추출하고 새로 강의가 끝나는 시간을 넣어줬습니다. * 여기서 가장 작은 숫자는 강의들 중 가장 빨리 끝나는 강의의 끝나는 시간입니다.

 

정답코드:

import sys
import heapq
input = sys.stdin.readline
 
q = []
num = int(input())
for i in range(num):
    q.append(list(map(int,input().split())))
q.sort()
 
nums_of_classroom = []
heapq.heappush(nums_of_classroom,q[0][1])
for i in range(1,num):
    if nums_of_classroom[0] > q[i][0]:
        heapq.heappush(nums_of_classroom,q[i][1])
    else:
        heapq.heappop(nums_of_classroom)
        heapq.heappush(nums_of_classroom,q[i][1])
 
print(len(nums_of_classroom))