[백준] 11000번 : 강의실 python

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

11000번: 강의실 배정

 

문제 정보

문제 유형 난이도 걸린 시간 스스로 구현 성공

그리디, 우선순위 큐, 자료구조, 정렬

골드5

1h

X

설계 방법

내가 설계했던 방법

• input 받은 것을 시작시간 기준으로 정렬
• 시작시간 S, 끝 시간 T list를 따로 선언 한 뒤 S를 돌면서 T가 이전 시작 시간들 보다 크거나 같으면 이전 강의실을 계속 사용하도록 함

정답 풀이 방법

① 현재 회의실에서의 회의가 끝나는 시간보다 다음 회의의 시작시간이 빠르면

회의실을 하나 추가로 개설한다.

② 현재 회의실에서 회의가 끝나는 시간보다 다음 회의의 시작시간이 느리면

현재 존재하는 회의실에서 이어서 회의 개최가 가능하다.

 

heap에 젤 먼저 시작하는 강의종료시간을 push한다.

그리고 1번 인덱스부터 ~ n번 인덱스까지현재 인덱스 강의 시작시간이 heap에서 루트노드 보다 작을 경우 heap에 강의 종료시간을 push를 한다. 강의 시작 시간이 heap 루트노드보다 크거나 같을 경우에는 루트 노드를 삭제하고 현재 인덱스 강의 종료시간을 push해준다.

heap에 삽입을 하면 최소힙을 유지를 하므로 heap에서 0 번째 인덱스는 무조건 가장 작은값을 유지한다. 즉 heap[0]에는 사용중인 강의실에서 가장 빨리 끝나는 값이 저장되어있다. heap[0] 에 저장된 값이 가장빨리 끝나는 강의실 이므로 강의가 시작하는 시간이 빠를 경우에는 heap[1],heap[2].. 에 저장된 강의실을 이용할 수 없다. 그러니 시작시간 < heap[0]일 경우에는 무조건 새 강의실을 사용해야 하므로 heappush를 해준다. heap[0]보다 강의 시작 시간이 클 경우에는 heap[0] 강의실을 사용할 수 있으므로 heap[0]을 삭제해주고 해당 강의 종료시간을 넣어주면 된다. 이렇게 반복한 뒤에 heap에 저장된 길이가 사용해야하는 강의실 개수이므로 출력하면 정답이다.

코드

내 코드(시간초과 발생)

import sys
input = sys.stdin.readline

n = int(input())
cnt = 0 
temp =[]
for _ in range(n):
  time = list(map(int, input().split()))
  temp.append(time)

# time[0] 기준으로 정렬 
# temp = sorted(temp, key=lambda x: x[0])
temp.sort(key=lambda x:x[0])

S = []
T = []

for i in temp:
  S.append(i[0])
  T.append(i[1])

for i in range(len(S)):
  if i == 0:
    cnt += 1
  for j in range(i):
    if T[j] <= S[i]:
      cnt += 1

print(cnt)

정답 코드

import sys
import heapq

heap = []
input = sys.stdin.readline
n = int(input())
arr = []
for i in range(n):
    a, b = map(int, input().split())
    arr.append([a, b])
arr.sort(key=lambda x: x[0])
heapq.heappush(heap, arr[0][1])  #첫번째 강의가 끝나는 시간을 넣음
for i in range(1, n):
    if heap[0] > arr[i][0]:
        heapq.heappush(heap, arr[i][1])
    else:
        heapq.heappop(heap)
        heapq.heappush(heap, arr[i][1])
print(len(heap))

시간 복잡도

$O(NlogN)$

heapq.heappush(pop)이 nlogn의 시간복잡도 가짐

어려웠던 점

내가 처음에 생각했던 대로 코드를 짜면 for문이 2번 중첩되기 때문에 시간초과가 날 수 밖에 없다

• 우선순위 큐나 자료구조에 대해 더 깊이 공부 필요
• time[0] 기준으로 sort하고 싶으면 그냥 time.sort()해도 되는 듯 이런 기초적인 것도 더 꼼꼼하게 공부할 것
• 처음에 문제를 접했을 때 꼭 시간복잡도 생각하기 반복문을 두 번 이상 중첩시키는 풀이는 최대한 피하기

참고 자료

https://velog.io/@slbin-park/백준-11000번-강의실-배정-파이썬

[백준] 11000 강의실 배정 (Python 파이썬)