[BOJ_11000] 강의실 배정 (python)

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

 

✅ 문제 설명

Si에 시작해서 Ti에 끝나는 N개의 수업이 주어질 때, 최소의 강의실을 사용해서 모든 수업이 가능하게 하자!

수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다. 즉 3초에 끝난 수업이 있다면 같은 강의실에서 다른 수업을 3초에 시작할 수 있다는 것이다.)

✅ 접근 방식

나는 우선순위 큐에 (시간, 타입)으로 튜플을 넣어줬다.

3
1 3
2 4
3 5

 

이런식으로 들어온다면

(1, "S")

(3, "E")

(2, "S")

(4, "E")

(3, "S")

(5, "E")

 

그래서 우선 순위큐를 돌면서 pop하면서 S이면 강의실을 하나 늘렸고, E면 강의실을 하나 줄였다.

근데 이때, 같은 시간이면 동시에 줄이고, 늘리고를 해야하므로, 현재 시간이랑 다음 pop할게 시간이 같으면 pop해주었다.

if len(h) != 0 and h[0][0] == time:
    continue

 

그리고 answer, 정답은 필요했던 최대 강의실 수!

 

✅ 코드 설명

import sys, heapq

h = []
N = int(sys.stdin.readline())
for i in range(N):
    Si, Ti = map(int, sys.stdin.readline().split())
    h.append((Si, "S"))
    h.append((Ti, "E"))

heapq.heapify(h)

들어온 값을 S, E로 구분하여 우선순위 큐에 넣어준다. 즉, (시간, 타입)을 우선순위 큐에 넣어준다.

그리고 heapq.heapify를 통해 우선순위 큐를 만들어준다.

 

count = 0
answer = 0
while h:
    time, type = heapq.heappop(h)
    if type == "S":
        count += 1
    else:
        count -= 1
    # print(f"({time},{type}) current count = {count}")
    if len(h) != 0 and h[0][0] == time:
        continue
    answer = max(answer, count)

print(answer)

현재 필요한 강의실 수를 계산할 count와, 답을 저장할 answer변수를 선언

우선순위 큐에 있는 걸 꺼내면서

time, type = heapq.heappop(h)

type이 "S" 면 count +=1 해주었고, 아니라면 "E"일 것이므로 count-=1 해주었다.

 

이때 여기가 중요하다.

if len(h) != 0 and h[0][0] == time:
    continue

h[0]을 통해 현재 우선순위큐의 상단을 보고, [0]을 통해 시간에 접근 (h[0][0]하면 다음 pop할 대상의 시간에 접근 가능)

같은 시간이라면 한번에 처리되어야하니까 continue를 해주어 heapq.heapop(h)해준다.

 

그리고 이 모든게 처리되었다면

answer = max(answer, count)

정답을 max(answer, count)로 갱신해준다!

max로 하는 이유는 수업이 별로 없어 강의실이 필요없어질 수 있기 때문에 시작부터, 마지막까지 지나오면서 최대 몇개의 강의실이 필요했는지로 갱신을 해주기 위해 max를 사용하자! (max를 안쓰고 그냥 answer=count로 갱신하면 1초엔 강의실 3개가 필요했는데 5초엔 강의실 0이 필요하다면, answer가 0으로 되어있어 오답이 된다... <- 내 경험담 ㅎㅎ)

 

✅ 최종 코드

# 강의실 배정
# Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데,
# 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다.
# Ti <= Sj인 경우, i수업과 j수업은 같이 들을 수 있다!

import sys, heapq

h = []
N = int(sys.stdin.readline())
for i in range(N):
    Si, Ti = map(int, sys.stdin.readline().split())
    h.append((Si, "S"))
    h.append((Ti, "E"))

heapq.heapify(h)

count = 0
answer = 0
while h:
    time, type = heapq.heappop(h)
    if type == "S":
        count += 1
    else:
        count -= 1
    # print(f"({time},{type}) current count = {count}")
    if len(h) != 0 and h[0][0] == time:
        continue
    answer = max(answer, count)

print(answer)

 

✅ 코멘트

- 옛날에 비슷한 문제 못 풀었던 기억이 나는데, 어디서 이렇게 푸는 걸 본 게 생각나 따라 해봤는데 맞았다! :> 그동안 본 게 많아 졌다는 생각이 들어 뿌듯하다.

 

나와는 다른 접근을 한 블로그 소개

https://c4u-rdav.tistory.com/43

[백준(BOJ)] #11000- 강의실 배정 (파이썬, Python3)

-> 나랑은 또 다른 접근을 한 블로그를 보았다. 참고하면 좋을 것 같다.

 

- 비슷한 문제 소개

https://school.programmers.co.kr/learn/courses/30/lessons/42884

프로그래머스