[알고리즘/그리디] 19598번 : 최소 회의실 개수 - python

링크 : https://www.acmicpc.net/problem/19598

19598번: 최소 회의실 개수

 

---

• 문제
• 소요시간: 15분(우선순위큐 개념 익히기)

---

• 설계하기(접근방법) 

1. 입력받기

입력받을 배열이 많으니

sys를 사용하자

 

2. 구현하기

이 문제의 배열 크기가  100,000이다. 즉 일반적인 정렬이나 완전 탐색으로는 시간이 초과된다

 

일단 문제를 해석하자면 이전 실버 1 문제의 회의실 배정과 비슷하다.

그 문제는 끝나는시간을 기준으로 정렬하고, 시작 시간을 비교하여 그리디로 풀었다

 

이 문제도 유사하게 끝나는 시간과 시작 시간을 비교해주어야 한다.

 

좀 간단히 생각해보면 회의실이 무한대이고 우리가 직접 회의실을 배정한다고 생각했을 때,

어떤 방법이 가장 효율적일까?

 

바로 A 회의 끝나는 시간과 B 회의의 시작 시간이 가장 가까울 때 이다.

1 3 이라면 3 5과 짝을 지어주는 것이 가장 회의 공백 시간을 줄일 수 있다.

그리고 1 3 3 5를 짝지어 줬다면 앞의 1 3 이라는 정보는 없어도 된다는 것을 알 수 있다.

이미 가장 효율적인 비교가 끝났기 때문에 돌아갈 필요가 없다.

 

그렇다면 우리가 알 수 있는 사실은 곧 들어갈 회의 시작 시간들을 오름차순으로 정렬해주어야

회의실들의 가장 이른 끝나는 시간과 비교할 수 있다.

 

회의실들의 끝나는 시간 중 가장 이른 시간은 heap을 통해 구현하여 연산을 log(n)으로 최소화시켜야 한다

 

즉

heap을 통해 항상 회의실들 중 최소 시간이 바로 비교되도록 구현하고,

 

정렬된 시작 시간들을 현재 회의실들 中 최소 시간과 비교해서

 

만약 새로 들어가는 시작 시간이 더 크다면 

최소 시간 정보를 pop 해준다.

 

만약 더 작다면 추가적으로 회의실이 필요한 것이니 count에 +1을 해주어 회의실을 늘려준다

 

두 케이스 공동적으로 회의가 들어갔으니 방금 넣은 회의의 마지막 시간을

heap에 push해주어 시간이 업데이트 될 수 있도록 한다

 

heap의 길이가 회의실과 같다고 생각하면 된다.`

 

3. 출력하기

회의실의 개수를 출력한다

 

 

---

• 코드(출력)

import sys, heapq

n = int(sys.stdin.readline())

cnt = 1
meeting_list = []

for i in range(n):
    start, end = map(int, sys.stdin.readline().rstrip().split())
    meeting_list.append([start,end])

meeting_list.sort(key = lambda x : x[0])

heap = [0]

for start, end in meeting_list:
    if start >= heap[0]:
        heapq.heappop(heap)
    else:
        cnt += 1
    heapq.heappush(heap, end)

print(cnt)

---

• 얻어갈 부분

1. 오랜만에 heap 구조를 봐서 개념을 다시 익혔다. 입력의 길이와 시간을 조사하여 일반적인 정렬로 풀 수 있는지, 특별한 알고리즘이나 자료구조가 필요한지 판단하자. heap 문제를 더 풀어 익혀보자