[백준] 1931번 회의실 배정: Python

 

문제 해결 포인트

회의를 하는 시간이 겹치지 않도록 최대한 많이 회의실을 사용해야 합니다. 이 조건으로 생각해볼 수 있는 아이디어는 다음과 같습니다.

 

• 회의에 걸리는 시간이 작은 순으로 정렬?
• 회의가 시작하는 시간이 빠른 순으로 정렬?
• 회의가 끝나는 시간이 빠른 순으로 정렬?

조금만 생각해보면, 회의가 끝나는 시간이 시작하는 시간보다 훨씬 중요하며 다음 회의가 시작하는 시간은 현재 회의가 끝나는 시간보다 늦거나 같아야 합니다.  새로운 회의시간이 길든 짧든 어차피 기존의 회의가 끝나는 시간보다는 새 회의의 시작시간이 늦어야 회의실을 빌리는게 가능하기 때문에, 회의시간의 길이는 생각보다 중요하지 않습니다. 단, 시작과 동시에 회의가 끝날수도 있으며 이 회의는 특별하게 다뤄야 합니다. 이 회의는 여러번 해도 겹치지 않기 때문에 카운트를 모두 해야합니다. 

 

코드 작성

회의들을 입력받고 회의가 끝나는 시간이 빠른 순으로 정렬하는것이 가장 기초적인 알고리즘입니다. 이 단계에서 다양한 인풋 케이스를 생각해보는것이 좋습니다.

 

인풋 케이스

• 평범한 회의
• 시작시간이 같은 여러개의 회의
• 끝나는 시간이 같은 여러개의 회의
• 시작하자마자 바로 끝나는 회의
• 겹치는 회의

# 입력 빨리 받기
import sys
input = sys.stdin.readline


N = int(input())
meetingList = []

for i in range(0, N):
	start, end = map(int, input().split())
	meetingList.append([start, end])

#끝나는 시간 기준 정렬
meetingList.sort(key=lambda x: x[1])

endTime = -1
count = 0

for meeting in meetingList:
	# 기존 회의가 끝나는 시간보다 새 회의의 시작시간이 늦거나 같다면
	if endTime <= meeting[0]:
		count += 1
		endTime = meeting[1]

print(count)

이 코드는 두번째, 네번째 인풋케이스를 처리할 수 없습니다. 끝나는 시간 기준으로만 정렬하고 시작하는 시간은 정렬되지 않기 때문입니다. 

반례 : [2 4] [3 5] [7 7] [6 7] [5 7]

반례의 [6 7] [5 7]이 가능한데도 [7 7]때문에 테스트되지 않습니다. 따라서, 만약 끝나는 시간이 같다면 시작시간이 빠른 순으로 정렬해서 endTime과 meeting[0]을 비교하도록 해야합니다. 여기서 파이썬의 강력한 문법이 등장합니다.

(이걸 몰라서 직접 구현하려고 뻘짓함 아아..)

meetingList.sort(key=lambda x: (x[1], x[0]))

끝나는 시간(x[1])을 우선순위로 먼저 정렬하고, 이후에 시작시간을 기준으로(x[0]) 다시 한번 부분정렬합니다.

이렇게 하면 다른 반례들을 직접 처리하지 않고도 문제를 쉽게 해결할 수 있습니다.