백준 문제 중 1931번, 그리디, ‘회의실 배정’
백준 문제 중 1931번
https://www.acmicpc.net/problem/1931
문제
한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.
입력
첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.
출력
첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.
풀이
이 문제의 핵심은 회의를 최대한 많이 하려면 따져야할 조건을 생각하는 것이다. 다음 두가지 조건을 생각할 수 있다.
- 회의가 빠르게 끝날수록 그 다음 선택지가 많아진다.
- 같은 시간에 회의가 끝난다면 시작시간이 더 큰 회의가 회의 시간이 적다.
그리디 문제로서 회의시간들을 1번 2번 조건에 따라 정렬한뒤 순서대로 선택하되, 이전 회의가 끝나는 시간과 다음 회의 시작시간이 같거나 다음 회의 시작이 클경우 가능한 회의 수 result에 1을 더해준다.
이를 코드로 구현할때 두가지 방법 정도가 떠올랐다.
Try 1
리스트로 그대로 진행
앞서 설명했던 과정을 그대로 코드로 옮기면 아래의 코드가 될것이다.
n = int(input())
meet = [None]*n
for i in range(n):
meet[i] = list(map(int,input().split()))
# meet를 x[1]순으로 정렬한 후 x[0]순으로 정렬
meet.sort(key = lambda x: (x[1],x[0]))
result = 0
# meet첫번째 회의는 시간도 가장적고 시작시간도 가장 빠르므로
# 무조건 result에 포함된다.
# 첫 회의가 끝나는 시간을 저장
meet_end = meet[0][1]
# 첫 회의 +1
result += 1
# 모든 회의를 스캔하며 조건에 맞는 경우 +1
for i in range(1,n):
if meet[i][0]>=meet_end:
meet_end = meet[i][1]
result += 1
print(result)
11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14
4
Try 2
heapq 모듈의 우선순위 큐로 구현
그리디에 가장 잘 어울리는 자료형인 우선순위 큐로 구현했으며 원하는 정렬 상태를 보장하기 위해 새로운 변수를 추가해서 큐를 구성했다.
import heapq
n = int(input())
meet = [None]*n
for i in range(n):
meet[i] = list(map(int,input().split()))
meet.sort(key = lambda x: (x[1],x[0]))
heap = []
# i를 통해 정렬순서를 보장한다.
for i in range(n):
heapq.heappush(heap,(i,meet[i][0],meet[i][1]))
result = 0
while heap:
x = heapq.heappop(heap)
result += 1
# 이전 회의의 종료시간보다 다음 회의의
# 시작시간이 늦거나 같을때까지 pop
while heap and x[2]>heap[0][1]:
heapq.heappop(heap)
print(result)
11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14
4
배운점
이 문제에서는 우선순위큐로 구현하는것과 리스트로 구현하는것의 속도차이가 크지않고 직관적인 측면에서 리스트가 더 유리했다.
Leave a comment