[백준][Python] 1931번 회의실 배정 문제 해설, 정답코드 (그리디 알고리즘)

 

❗ 문제 접근법, 아이디어

1. 회의가 빨리 끝날수록 뒤에 더 많은 회의를 할 수 있다.

2. 회의가 끝나는 시간이 같다면, 회의 시작 시간이 빠른 회의가 우선된다.

 

2번이 무슨 소리냐면,

# 1시에 시작하고 8시에 끝나는 회의, 8시에 시작하고 8시에 끝나는 회의
(1, 8) (8, 8)

이렇게 두 회의가 있을 때 (1, 8) (8, 8) 순서로 두면 두 회의를 다 진행할 수 있지만,

(8, 8) (1, 8) 순서로 두면 앞에 있는 회의 1개만 진행할 수 있다.

 

그래서 회의 시간을 정렬할 때,

끝나는 시간 순으로 정렬하고 시작하는 시간 순으로 두 번 정렬해야 한다.

# 끝나는 시간 기준으로 정렬하고 시작하는 시간 기준으로 정렬
arr.sort(key=lambda x: (x[1], x[0]))

arr은 회의 시간을 담은 리스트이다.

파이썬의 sort() 함수는 key 매개변수를 사용하면 '특정한 데이터 기준'으로 정렬할 수 있다.

 

>> 고로 그리디 알고리즘 사용!!

가장 회의가 빨리 끝나는 시간을 선택한다는 점에서 "현재 상황에서 가장 최선의 선택"을 하는 그리디 알고리즘이 적용된다고 볼 수 있다.

 

❗ 정답 코드

import sys

n = int(sys.stdin.readline())
arr = []
for _ in range(n) :
    a,b = map(int, sys.stdin.readline().split())
    arr.append([a,b])

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

count = 0
last = 0
for a,b in arr :
    if a >= last :
        count += 1
        last = b

print(count)

회의가 끝나는 시간을 last로 두고

last보다 큰 최소한의 회의 시작 시작(=a)가 있다면

count를 1 올리는 식으로 풀면 된다.