[BOJ] 백준 1931 회의실 배정 (Python)

문제

1931번: 회의실 배정

 

문제 해석

접근 방법

그리디 알고리즘과 정렬을 사용해 풀 수 있는 문제입니다. 회의실을 가능한 한 많이 사용해야 하므로 일찍 끝나는 회의부터 순서대로 선택하면 됩니다.

 

풀이 과정

1. 일찍 끝나는 순서대로 회의들을 정렬
2. 직전에 선택한 회의와 시간이 겹치지 않도록 다음 회의를 선택

 

일찍 끝나는 회의부터 선택하기 위해 회의의 종료 시간을 기준으로 오름차순으로 정렬합니다. 하지만 회의의 종료 시간만 기준으로 삼으면 풀리지 않는 예외 케이스가 존재합니다. 시작과 동시에 끝나는 회의가 존재하기 때문입니다.

 

 

만약 주어진 회의 시간이 다음과 같다고 가정해보겠습니다. (N = 3)

3
1 2
3 3
2 3

 

 

회의 종료시간을 기준으로 오름차순 정렬했을 때 결과는 다음과 같습니다. 이 리스트를 맨 앞부터 순서대로 탐색할 경우, (3, 3)의 종료 시간보다 (2, 3)의 시작 시간이 빠르므로 선택에서 제외됩니다.

 [(1, 2), (3, 3), (2, 3)]

 

 

이러한 경우를 고려하기 위해서 회의 종료 시간이 동일할 경우에는 회의 시작 시간을 기준으로 오름차순 정렬해야 합니다. 이 기준에 따라 다시 정렬하면 다음과 같은 결과가 나옵니다. 이 경우에는 (2, 3) 이후에 (3, 3)을 탐색하므로 두 회의를 모두 선택할 수 있게 됩니다.

[(1, 2), (2, 3), (3, 3)]

 

전체 코드

from sys import stdin

N = int(stdin.readline().rstrip())
table = [list(map(int, stdin.readline().rstrip().split())) for _ in range(N)]

# x[1](회의 종료 시간)을 기준으로 오름차순 정렬한 후 x[2](회의 시작 시간)을 기준으로 오름차순 정렬
table.sort(key=lambda x: (x[1], x[0]))

cnt = 0
temp_end = 0

for t in table:
    if temp_end <= t[0]:
        temp_end = t[1]
        cnt += 1

print(cnt)

 

회고

• 등호 포함 여부, 예외 케이스 등을 고려하지 않은 작은 실수 때문에 풀이 시간이 길어졌다. 코드를 제출했을 때 한 번에 통과할 수 있도록 문제를 꼼꼼히 읽는 습관을 들이자.