[그리디 알고리즘] ★ 11000번 - 강의실 배정

[백준] 11000번 - 강의실 배정

(풀이1) 시간 초과된 실패 코드

1) 문제 해결 아이디어

아이디어는 쉽게 떠올렸으나 시간초과로 실패하였다.

input() 문제인가 싶어 sys.stdin.realine()으로 대신했으나 또 시간초과가 되었다.

 

for문 내에서 해당 강의를 room에 넣고 나면 다시 room을 끝 값 기준으로 오름차순 정렬하는 것을 반복하도록 하였는데 이런 방식으로 인하여 시간초과가 생기는 것 같았다.

시간초과 문제를 해결하기 위해 다른 방식으로 구현할 필요성을 느꼈다.

 

2) 소스코드

import sys

n = int(input())  # 수업 수
# n 개의 수업 정보
arr = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

arr.sort()
# 첫 번째 강의 
room = [arr[0]]
#res = 1  # 강의실 개수


for i in range(1, n):
  # 강의실 배치하기
  for j in range(len(room)):
    room.sort(key=lambda x:x[1])
    # 현재 강의의 시작값이 비교 강의의 끝값보다 크거나 같으면
    if(room[j][1] <= arr[i][0]):
      room[j] = arr[i]  # 현재 강의실에 배정
      break
    # 모든 강의실이 꽉차 있으면
    if(j == len(room) - 1):
      room.append(arr[i])   # 새로운 강의실에 배정

#print(room)
print(len(room))

 

(풀이2) 우선 순위큐를 

1) 문제 해결 아이디어

해당 문제는 시간초과를 해결하기 위해 우선순위 큐를 사용하는 것이 핵심이다.

아직 파이썬에서 우선순위큐를 활용하는 법을 배우지 않았기 때문에 틀릴 수 밖에 없었던 문제이다.

 

먼저 수업(schedule)을 강의 시작값을 기준으로 오름차순 정렬한다. 사실상 아무런 조건 없이 정렬하는 것과 주석한 부분처럼 key 값을 주는 것과 결과는 동일하다.

 

정렬 후, 현재 강의의 시작값을 끝값이 가장 적은 강의의 끝값과 비교한다.

전자가 크다면 기존 강의실에 강의를 배치할 수 없으므로 즉, 새로운 강의실에 배치해야한다.

현재 강의의 끝값을 우선순위 큐에 추가한다.

후자가 크다면 기존 강의실에 강의를 배치할 수 있으므로 즉, 기존 강의실의 수업을 빼고 현재 강의를 배치해야한다.

우선순위큐에서 가장 작은 원소인 끝값을 꺼내고 현재 강의의 끝값을 추가한다.

 

그렇게 첫번째 강의를 제외한 모든 강의에 대해 이를 반복한 결과,

강의실에 배치한 수업(room)의 길이가 최소로 사용할 강의실의 개수이다.

 

2) 소스코드

import heapq
import sys

n = int(input())  # 수업 수
# n 개의 수업 정보
schedule = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
schedule.sort()   # 시작값 기준 오름차순 정렬
#schedule.sort(key=lambda x:x[0])
 
room = []  # 강의실
heapq.heappush(room, schedule[0][1])  # 끝값 추가

for i in range(1, n):
  # 다른 강의 끝값 최솟값이 현재 강의 시작값보다 크다면
  if(room[0] > schedule[i][0]):
    # 새로운 강의실에 배치
    heapq.heappush(room, schedule[i][1])  # 현재 강의 끝값 추가
  # 다른 강의 끝값 최솟값이 현재 강의 시작값보다 작거나 같다면
  else:
    # 현재있는 강의실에 배치(변경=삭제->추가)
    heapq.heappop(room)  # 변경할 강의 삭제
    heapq.heappush(room, schedule[i][1])  # 현재 강의 끝값 추가

print(len(room))

 

<heapq 모듈>

리스트를 최소 힙처럼 다룰 수 있게 함

빈 리스트 생성 후 heapq 함수 호출시 해당 리스트를 인자로 넘겨야 한다.

import heapq heap = []	heapq 모듈 import 빈 리스트 생성
heapq.heappush(heap, item)	item을 heap에 추가
heapq.heappop(heap)	heap에서 가장 작은(우선순위가 가장 높은) 원소를 pop & return (비어 있는 경우 IndexError가 호출됨)

 

[참고] https://littlefoxdiary.tistory.com/3

[Python] 힙 자료구조 / 힙큐(heapq) / 파이썬에서 heapq 모듈 사용하기

 

[참고] https://kyoung-jnn.tistory.com/entry/%EB%B0%B1%EC%A4%8011000%ED%8C%8C%EC%9D%B4%EC%8D%ACPython-%EA%B0%95%EC%9D%98%EC%8B%A4-%EB%B0%B0%EC%A0%95

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