[백준/파이썬] 11000 : 강의실 배정

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

11000번: 강의실 배정

문제 요약 : 강의의 시간시간과 끝나는 시간이 주어진다. 모든 수업이 가능한 최소의 강의실 개수는?

 

그리디 알고리즘을 공부하다가 활동 선택문제의 예시를 찾다가 풀게 된 문제

내가 찾고자 했던 문제는 회의실이였어서, 처음에 문제를 잘못 읽고 접근 했었다.^^;

 

우선순위큐를 적절히 활용해야 했던 문제!

그리디 알고리즘과 우선순위 큐에 대한 내용은 요기에!

 

 

시도 )

회의실 문제를 풀고, 유사한 문제겠지 하고 접근했다가 낭패를 봤다.

 

일단 내 생각의 흐름은 이러하였다.

 

1. 강의들(time)을 빨리 끝나는 순으로 정렬한다.

2. 힙에 가장 빨리 끝나는 강의의 끝나는 시간을 넣는다.

3. 강의들을 1부터 반복문을 돌려서 heap의 루트노드(최소값, 배정된 강의실 중 가장 빨리 끝나는 시간)에 저장된 값과 비교한다.

 

3-1. 현재 강의의 시작 시간 >= heap의 루트 노드 일 경우, 배정된 강의실을 사용할 수 있다.

=> for문을 뒤에서부터 돌려서 현재 강의 시작시간보다 작거나 같은 수 중 가장 늦게 끝나는 강의실에 현재 강의를 배정한다.(pop해줌)

 

3-2. 현재 강의의 시작 시간 < heap의 루트 노드 일 경우, 강의 실을 새로 배정해야한다.

4. 현재 강의의 끝나는 시간을 heap에 넣어준다.

 

3-1이 저렇게 복잡하게 나온 이유는, 

8
1 8
9 16
3 7
8 10
10 14
5 6
6 11
11 12

를 넣으면 답이 3이 나와야하는데 자꾸 5가 나왔기 때문이다.

그 이유는, 빨리 끝나는 순으로 정렬하면 뒤에 나오는 값의 시작 시간이 더 빠를수도 있기 때문이었다.

 

그래서 나는 가장 유사한 값들에 배정되면 된다고 1차원 적으로 생각했다.

그런데 그러기 위해선 heap을 쓰는데도 불구하고 for문을 통해 비교를 해줬어야 했다. 또한, heappop이 아닌 pop을 사용하기도 했다.

# 강의실 배정
import sys
import heapq
input = sys.stdin.readline

N = int(input())
time = []

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

heap = [time[0][1]]
for i in range(1,N):
    if heap[0] <= time[i][0]: 
        for j in range(len(heap)-1,-1,-1) :
            if heap[j] <= time[i][0] :
                heap.pop(j)
                break
    heapq.heappush(heap,time[i][1])

print(len(heap))

시간초과가 떴다 그것도 2% 만에...

문제를 풀기 위해선 아예 새로 생각을 했어야했다.

 

 

풀이 )

결론적으로 말하면, 회의실 문제에 사로잡혀서 강의실을 빨리 끝나는 순으로 정렬한 것 부터 잘못됐다.

 

이 문제는 무엇보다 시간초과가 나지 않는 것이 중요하다. 그를 위해 heap을 사용한 것이다.

저 위에서 heap을 쓰면서 pop(i)값을 쓰는게 잘못된 접근이었던 것.

 

회의실은 가장 빨리 시작하는 순으로 정렬한다.

그래야 heap을 강의 끝나는 시간을 갱신할때, 다른 비교없이 heappop만으로 끝낼 수 있기 때문이다.

 

가장 빨리 시작하는 순으로 정렬한다면, 뒤에 들어오는 값 때문에 for문을 돌려줄 필요가 없다.

즉, heappop을 해주고, 뒤의 들어오는 강의의 시작시간이 더 짧으면 어쩌지? 라는 고민을 해줄 필요가 없다.

# 강의실 배정
import sys
import heapq
input = sys.stdin.readline

N = int(input())
time = []

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

heap = [time[0][1]]
for i in range(1,N):
    if heap[0] <= time[i][0]:
        heapq.heappop(heap)
    heapq.heappush(heap,time[i][1])

print(len(heap))

 

질문게시판을 보니 나처럼 정렬해서 낭패를 본 사람이 없었다.

문제를 많이 풀어보는 것은 시야를 넓히니까 좋지만, 풀이 하나에 사로잡히면 반대로 시야를 좁게 하는 것 같다.

refresh의 중요성~