[백준/알고리즘/python/java] 11000번 - 강의실 배정

이미지를 누르면 문제 링크를 보실 수 있습니다.

이미지를 누르시면 문제 링크를 보실 수 있습니다.

작년에 풀었던 문제인데, 제대로 이해를 하지 않고 넘어갔었던 느낌이 들어 다시 풀어본 문제이다.

거의 기억이 안나서 새로 푼 문제나 다름이 없었는데, 총 3번의 시련을 겪었다.

 

가장 먼저, 잘못된 로직으로 문제를 풀어나가기 시작했다.

예를 들어, 입력값이

3

1 98 

98 99

99 100 

이 주어졌다고 하면, 답은 어떻게 나올까?

답은 3이 나와야 한다고 생각한다면, 나와 똑같은 실수를 한 셈이다.

답은 1이 나와야 한다. 1~98 , 98~99, 99~100 이렇게 겹치지 않고, 1강의실만을 이용해서 강의를 배정할 수 있기 때문이다.

 

첫 번째 시련을 겪고, 빠르게 로직에 대해서 생각해봤다.

대충 로직은 이러했다. 

입력 받은 "강의가 시작되는 시간"과 "강의가 끝나는 시간"을 

강의 리스트를 (강의 시작시간, 강의 끝나는 시간) 형태(리스트이든 튜플이든)로 새로운 리스트에 담는다.

그 새로운 리스트에는 모든 강의의 쌍이 담겨져 있을 것이다.

 

그렇다면, 이제는 시작시간을 기준으로 오름차순 정렬을 해야할 차례이다.

강의시간이 앞선 강의부터 시작되어야 하는 것이 당연하기 때문이다.

 

예를 들어, 

[(1,2), (1,3), (2,4), (3,5), (4,5)] 순으로 새로운 강의리스트에 담겨있다고 하자.

그러면, 이 강의리스트를 돌면서, 강의가 끝나는 시간들을

또 다른 새로운 리스트에 저장해나가는 것이 관건인 문제였다. 강의가 끝나는 시간을

체크해야 빈 강의실에 새로운 강의를 넣을 수 있는 판단이 가능하기 때문이다.

 

강의가 끝나는 시간 중에서도 가장 작은, 그러니까 가장 빨리 끝나는 시간(=min_until)을 계속해서 

체크해야 하는데, 이 부분의 조건문을 잘못한 것이 두 번째 시련이었다.

heapq를 써야하는 것은 제대로 했지만, 강의의 시작시간과 min_until 시간의 비교, 시작시간이 달라지고 또 같아지는 것에 대해 불필요하게 비교를 하였고, 그러다보니 코드는 조건문으로 계속해서 길어지게 되었다.

 

예외를 다 잡아도, 또 다른 예외가 계속 발생하게 되었고, 뫼비우스의 띠 마냥 한 예외를 잡으면, 기존에 잡았던 예외가 안되는 상황이 반복되었다. 차분하게 문제를 다음날로 미루고 다시 풀어봤는데,

조건문에 대해 생각해봤다.

 

결국, 강의가 끝나는 시간이 담긴 힙큐에서 가장 빨리 끝나는 시간에 대한 수와 다음에 순회하는 강의의 시작시간에 대한 비교를 할 때, 다음 강의시작 시간이 기존에 시작했던 강의 중 가장 빨리 끝나는 시간보다 작다면, 강의실을 하나 추가할 수 밖에 없고, 크거나 같다면, 기존 강의실에서 진행됐던 강의가 끝나고 비어있다는 사실이므로, 굳이 강의실을 추가할 필요가 없다는 게 이번 문제의 로직이었다.

 

3번의 시행착오 끝에 코드는 간결해졌고 코드는 아래와 같다.

import sys
input = sys.stdin.readline
import heapq 

n = int(input())   # 수업 수 n을 입력받기 
lecture = []  # 강의 리스트 생성
for _ in range(n):  # n을 돌면서,
    start_to_end = list(map(int,input().split())) # start_to_end를 리스트화 하고
    lecture.append(start_to_end)  # lecture에 append해준다.
 
lecture= sorted(lecture, key = lambda x : x[0]) # lecture를 x[0](강의 시작하는 시간)오름차순으로 정렬한다.

start = lecture[0][0] # 맨 처음 시작하는 lecture의 시간은 lecture[0][0] (이거는 문제푸는데에 사용 안됐다.)
min_until = lecture[0][1] # 맨 처음 시작하는 lecture 끝나는 시간은 lecture[0][1]
min_until_list = [min_until]  # min_until_list라는 리스트에 min_until을 넣어주고 시작한다.
heapq.heapify(min_until_list) # heap화 시켜준다.

total = 1 # 강의한개 넣고 시작하니까 total 강의실 개수도 1개로 시작

for x in lecture[1:]: # lecture의 1번째 강의부터 순회하기 시작(맨 처음 강의를 이미 계산한 상태에서 시작한 것이므로)
    if x[0] < min_until_list[0]: # 지금 순회하는 강의의 시작 시간이 min_until_list의 최소값보다 작으면(min_until_list는 힙이기 때문에, 제일 작은 시간이 앞으로 온다.)
        # 강의실 1개 더 추가해야 한다.
        total += 1  
        heapq.heappush(min_until_list,x[1]) # 그리고 지금 순회하는 강의의 끝나는 시간도 역시 집어넣어준다.
    else:   # 시작 시간이 크거나 같으면 빈 강의실이 있다는 것(따로 강의실을 추가해주지 않아도 된다는 것)
        heapq.heappop(min_until_list) # min_until_list의 가장 작은 수를 pop해준다.(맨 앞 값이겠다.)
        heapq.heappush(min_until_list,x[1]) # 그리고 지금 순회하는 강의의 끝나는 시간을 집어넣는다.

print(total)  # 최소로 사용하게 되는 총 강의실 개수 출력

 

작녀에 풀었던 풀이도 이와 같은 로직이지만 리스트 컴프리헨션 등의 조금 더 간결하게 코드를 풀었었다.

코드는 아래와 같다.

import sys
input = sys.stdin.readline
import heapq

N = int(input())

timeTable = [list(map(int,input().split())) for _ in range(N)]
timeTable.sort(key=lambda x: x[0])

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

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

print(len(queue))

그래도, 로직을 제대로 이해하고 푼 것 같아 시간이 좀 걸렸지만 보람차다.