[Python][백준 1379,1374][우선순위 큐,정렬] 강의실, 강의실 2 - 컴도리돌이

1374번: 강의실

1379번: 강의실 2

---

풀이 과정 - 강의실 

 

1. 강의실을 최소로 배정하는 개수를 구해야 한다.

2. heap에서 시작시간, 끝나는 시간, 강의실 번호를 heap push를 한다.

3. 첫 번째로 시작시간이 가장 짧은 값을 heap pop을 시킨다.

4. 가장 짧은 시작시간을 가진 스케줄의 끝나는 시간을 q에 heap push를 한다.

5. while문 -> heap에서 pop을 시켜서 시작 시간과 q의 top의 끝나는 시간과 비교해서 시작시간이 더 크면 강의실 배정할 필요 없기 때문에 q에 있는 값을 pop을 해준다.

6. 5에서 pop 한 값에서 끝나는 시간을 q에 넣어준다. (5-6번 반복)

7. 시작시간이 끝나는 시간보다 작아서 강의실을 배정하지 못한 스케줄들이 q에 남아있다. 그러므로 q의 크기를 출력해준다.

 

풀이 코드

import sys,heapq; input = sys.stdin.readline
heap = []
q = []

for _ in range(int(input())) :
  num,start,end = map(int,input().split())
  heapq.heappush(heap,[start,end,num])
start,end,num = heapq.heappop(heap)
heapq.heappush(q,end)
while heap :
  start,end,num = heapq.heappop(heap)
  if q[0] <= start :
    heapq.heappop(q)
  heapq.heappush(q,end)
print(len(q))

반응형

---

풀이 과정 - 강의실 2

 

1. 입력받은 스케줄을 시작시간과 끝나는 시간 순으로 정렬을 시킨다.

2. 각 스케줄마다 어떤 강의실을 배정하였는지 출력해야 한다. 그러므로 lecture이라는 정답 출력 배열을 크기 n+1로 0 값으로 할당해주었다.

3. 강의실 번호를 순차적으로 배정하고, 만약 강의실 1처럼 시작시간이 끝나는 시간보다 큰 경우 동일한 번호를 배정해주기 위해서 강의실 번호를 n번까지 heap push를 해주었다.

 

4. while반복문 -> 정렬된 스케줄을 순차적으로 진행시킨다. 만약 minHeap 배열에 값이 있을 경우 minHeap의 끝나는 시간과 순차적으로 진행되는 스케줄의 시작시간보다 작을 경우 minHeap의 top을 pop 해준다.(해당 배정된 room 값을 재사용)

5. room 번호를 pop 해준다. 해당 room번호와 끝나는 시간을 minHeap에 넣어준다.

6. 해당 스케줄 번호를 5에서 pop해준 강의실 번호로 저장해준다.

 

풀이 코드

 

 

import sys, heapq
input = sys.stdin.readline
n = int(input())
arr = sorted([list(map(int,input().split())) for _ in range(n)],key= lambda x : (x[1],x[2]))
lecture = [0 for _ in range(n+1)]
room = []
for i in range(1, n+1):
    heapq.heappush(room, i)

minHeap = []
print(arr)
for num,start,end in arr:
    while minHeap and minHeap[0][0] <= start:
        e, r = heapq.heappop(minHeap)
        heapq.heappush(room, r)

    r = heapq.heappop(room)
    heapq.heappush(minHeap, [end, r])
    lecture[num] = r

print(max(lecture))
for x in lecture[1:]:
    print(x)