백준)11000_강의실 배정.python

<문제 접근 방법>

1. 먼저 가장 적은 강의실을 사용하기 위해선 시작시간과 종료시간이 빠른 수업을 먼저 배치한다.

따라서 시작시간이 빠른 순서대로, 시작 시간이 같다면 종료시간이 빠른 순서대로 정렬을 해야한다.

2. 수업을 강의실에 배치할 때 종료시간이 수업의 시작시간보다 같거나 빠른 경우 같은 강의실에서 강의를 할 수 있다.

3. 수업을 강의실에 배치할 때 종료시간이 수업의 시작시간보다 늦는 경우 새로운 강의실이 필요하다.

 

<솔루션 1>

scd는 n개의 [시작시간, 종료시간]를 가지고 있다.

이 솔루션은 시간초과가 발생하였는데 오답의 원인을 생각해보니 N의 개수가 20만개이기 때문에 O(N^2)의 방법으로는 불가했다.

scd가 빌때까지 순회를 하면서 skip(이전 종료시간)보다 현재 노드의 시작시간이 더 빠른 경우를 건너뛰었으며 그렇지 않는 경우에 대해선 rm 리스트에 사용된 scd를 넣고 반복문의 마지막에 scd에 rm을 빼주었다. 

 

<소스코드 2>

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

scd = []
for i in range(n):
    scd.append(list(map(int, sys.stdin.readline().split())))
scd.sort()    

count = 0
rm = []
while scd:
    count += 1
    skip = 0
    for i in range(len(scd)):
        if scd[i][0] < skip:
            continue
        skip = scd[i][1]
        rm.append(scd[i])
    scd = [x for x in scd if x not in rm]
print(count)

 

<솔루션 2>

위의 케이스를 제출하고나서 이중 for문을 사용시 시간초과가 나는 것을 알았다.

최소값을 구하려한다해도 remove(min(list))와 같이 해야할텐데 결국 이중for문이 되어버린다.

그래서 최솟값을 쉽게 구하기 위해 찾아보던중 heapq 모듈에 대해 알게되었다.

heapq는 다음 사이트를 통해 공부하였다.

(https://www.daleseo.com/python-heapq/)

 

heapq 모듈은 이진트리 기반의 최소 힙 자료구조를 제공한다.

최소 힙은 원소들을 항상 정렬된 상태로 추가해주며, 가장 작은 값은 인덱스 0 즉, 이진 트리의 루트에 위치하게 된다.

힙에 원소 추가: heapq.heappush(리스트명, 원소) - 리스트에 정렬하며 원소를 추가한다

힙에 원소 제거: heapq.heappop(리스트명) - 리스트의 최소값(인덱스 0)을 제거한다

 

heap엔 종료시간을 넣었으며 종료시간이 가장 빠른 것을 먼저 체크하였다.

heap에 저장된 가장 빠른 종료시간보다 시작시간이 크다면 해당 종료시간을 빼버리고 종료시간을 새로 추가했으며,

시작시간보다 종료시간이 더 이후인 경우엔 새로운 강의실이 필요하기 때문에 heap에 새롭게 종료시간을 추가했다.

 

<소스코드 2>

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

scd = []
for i in range(n):
    scd.append(list(map(int, sys.stdin.readline().split())))
scd.sort()  

import heapq

heap = []

heapq.heappush(heap, scd[0][1])
for i in range(1,n):
    if scd[i][0] >= heap[0]:
        heapq.heappop(heap)
    heapq.heappush(heap, scd[i][1])
print(len(heap))