백준 11000 강의실 배정 파이썬 풀이

난이도 : 골드5

풀이일 : 2404114

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

11000번: 강의실 배정

---

문제 캡쳐

---

아이디어

• 각 강의의 시작, 끝 시간을 입력받아 오름차순으로 저장한다.
• 매 강의 정보에 대해 이전 강의의 끝 시간이 현재 강의의 시작 시간보다 작은 것이 있는지 탐색하고, 조건에 부합하는 것이 있다면, 앞 강의를 현재 강의 배열에서 제거한다.
• 조건에 해당하지 않건, 해당하건 강의의 정보를 현재 강의 배열에 추가한다. 추가 후, 현재 강의 개수가 이전에 저장된 수보다 많은지 확인하고, 변수를 업데이트한다.

---

전체 풀이코드

import sys, heapq

N = int(sys.stdin.readline())
lectures = []  # 강의 정보
for _ in range(N):
    s, e = map(int, sys.stdin.readline().split())
    lectures.append([s, e])
lectures.sort()  # 강의 시간 정렬

maxi = 0  # 최대 강의실 수
rooms = []  # 사용하는 강의실 강의 종료 시간
for s, e in lectures:
    if rooms and s >= rooms[0]:
        heapq.heappop(rooms)
    # 현재 강의 정보 저장
    heapq.heappush(rooms, e)
    # 강의실의 수 재할당
    maxi = max(maxi, len(rooms))

print(maxi)

---

상세 풀이코드

N = int(sys.stdin.readline())
lectures = []  # 강의 정보
for _ in range(N):
    s, e = map(int, sys.stdin.readline().split())
    lectures.append([s, e])
lectures.sort()  # 강의 시간 정렬

• lectures : 진행되는 강의의 시작시간, 종료 시간을 저장하는 이차원 배열이다.
• 전체 강의를 입력받은 후, 강의들을 시작 시간을 기준으로 오름차순으로 정렬해준다.
• heapq를 사용했었는데, heapq로 하나씩 lectures에 push 할 때보다 append 후 sort 하는 과정이 시간이 더 빠르게 나와 해당 방법으로 기록하였다.

 

maxi = 0  # 최대 강의실 수
rooms = []  # 사용하는 강의실 강의 종료 시간
for s, e in lectures:
    if rooms and s >= rooms[0]:
        heapq.heappop(rooms)
    # 현재 강의 정보 저장
    heapq.heappush(rooms, e)
    # 강의실의 수 재할당
    maxi = max(maxi, len(rooms))

print(maxi)

• maxi : 강의 추가 시 마다 저장된 숫자와 rooms의 길이를 비교해 더 큰 값을 저장할 변수다.
• rooms : 현재 사용하는 강의실에서 진행되는 강의들의 종료 시간을 저장한다.
• for 반복문 : lectures에 저장된 강의들의 시작, 끝 시간 정보를 가지고 반복한다.
  • if문 : 만약 현재 사용되는 강의실에 현재 강의의 시작 시간보다 빨리 끝나는 강의가 있다면, 빨리 끝난 강의를 rooms에서 제거한다.
  • 제거한 경우에도, 제거하지 않은 경우에도 새로운 강의의 정보는 추가해야 하므로 모두 현재 강의의 종료 시간을 rooms에 추가해준다.
  • rooms에 강의를 추가한 후, 현재 저장된 maxi와 현재 rooms의 길이 중 긴 것을 maxi에 저장한다.
• 저장되어 있는 maxi를 출력한다.

---

느낀점

• 얼마전부터 문제를 풀고 나서 가능한 다른 방법들과의 성능을 비교해보면서 여러번 채점을 넣고 있는데, 이게 좀 재미있다. 왜 어떤 건 속도가 더 빠른지, 어떤건 메모리를 덜 사용하는지 고민하다보면 역시 시간복잡도 공부를 해야겠다 싶어지지만