백준 1931번 : 회의실배정
N개의 회의의 시작시간과 종료시간를 입력받고
한 개의 회의실에서 진행할 수 있는 회의의 최대 개수를 출력하는 문제입니다.
대표적인 활동 선택(Activity Selection)유형의 문제로 그리디 알고리즘을 사용하는 문제입니다.
설계 & 구현
일단 그리디 알고리즘인 것을 알고 있으니 설계과정은 간단해집니다.
무엇을 기준으로 할지만 파악하면 되겠습니다.
선택지는 시작시간과 종료시간, 2가지인데 빠르게 종료하는 회의부터 선택해야 최대한 많은 회의를 포함할 수 있을테니 종료시간이 기준이 되어야 합니다.
여기서 시작시간과 종료시간이 같을 수 있다라는 조건을 고려해야 합니다.
3 - 3이라는 회의는 3시에 시작해서 3시에 끝나는 회의입니다.
3 - 4를 먼저 선택한다면, 현재 회의실의 종료시간은 4시로 바뀝니다.
그 이후엔 3 - 3회의를 포함하지 못하게 되어버리므로
가장 많은 회의를 포함해야 하는 최적해가 아니게 됩니다.
따라서 종료시간이 같다면, 시작시간이 더 빠른 회의 먼저 확인해야 합니다.
구현
입력에 대한 설명은 넘어가겠습니다.
저는 리스트에 튜플 형태로 저장했습니다.
N = int(input())
table = []
for i in range(N):
s,e = map(int, input().split())
table.append((s,e))결과를 나타낼 선택한 회의의 개수 와 현재까지 선택한 회의들의 종료시간을 나타낼 변수가 필요합니다.
count = 0 #회의 개수
cur_end = 0 #현재까지 배정된 회의들의 종료시간설계단계에서 종료시간을 기준으로 오름차순, 종료시간이 같다면 시작시간부터 오게끔 정렬해야겠다고 구상했었습니다.
파이썬의 내장 함수인 sort()는 퀵정렬로 구현되어 있기 때문에
시작시간을 기준으로 정렬한 후, 그 다음에 종료시간을 기준으로 정렬하면 됩니다.
#시작시간으로 오름차순 -> 종료시간으로 오름차순
table.sort(key=lambda a: a[0])
table.sort(key=lambda a: a[1])이제 정렬까지 했으니 탐색만 남았습니다.
입력받은 회의 전체에 대해서 진행할 반복문을 작성해보겠습니다.
-
리스트에서 회의의 시작시간 S와 종료시간 E를 가져온다.
-
회의의 시작시간 S가 cur_end보다 크거나 같다면 그 회의를 포함한다.
1) cur_end를 E로 갱신한다.
2) 회의의 개수 count를 1 증가시킨다. -
이 과정을 리스트 전체 요소에 대해 반복한다.
코드로 보면 더 쉽습니다.
#리스트 전체 요소에 대해
for S,E in table:
#시작시간이 cur_end보다 늦다면 그 회의를 포함함
if S >= cur_end:
#cur_end 갱신
cur_end = E
#회의 개수 1 증가
count += 1그리디 문제 답게 설계만 하고 나면 구현은 굉장히 간단한 편입니다.
입력의 개수가 크지 않아서 퀵정렬을 사용했지만, 우선순위 큐를 사용해보는 것도
고려해볼만 한 것 같습니다.
전체코드
import sys
input = sys.stdin.readline
N = int(input())
table = []
for i in range(N):
s,e = map(int, input().split())
table.append((s,e))
count = 0 #회의 개수
cur_end = 0 #현재까지 종료시간
#시작시간으로 오름차순 -> 종료시간으로 오름차순
table.sort(key=lambda a: a[0])
table.sort(key=lambda a: a[1])
# print(table)
for S,E in table:
if S >= cur_end:
cur_end = E
count += 1
print(count)