백준 1931번 회의실 배정 파이썬

https://www.acmicpc.net/problem/1931

1931번: 회의실 배정

 

내 답안

N = int(input())
M = []
for i in range(N):
    start_time, end_time = map(int, input().split())
    M.append((start_time, end_time))

# 끝나는 시간으로 시간대 정렬
M.sort(key=lambda x: (x[1], x[0]))

et = cnt = 0
for start_time, end_time in M:
    if start_time >= et:
        et = end_time
        cnt += 1
print(cnt)

---

 

# 끝나는 시간으로 시간대 정렬
M.sort(key = lambda x: (x[1], x[0]))

요 코드는 (a,b) 튜플들이 여러개 있을때 b기준으로 리스트를 정렬 한다는 것이다.

예를 들어

[(1, 6), (2, 4), (3, 5)] 이 리스트를 람다식으로 정렬을 한다면

[(2, 4), (3, 5), (1, 6)] 이런 식으로 정렬이 된다는 뜻이다.

 

예시를 한번 더 들어 보자면

[(8, 12), (7, 11), (8, 11)]  --> [(7, 11), (8, 11), (8, 12)] 이렇게 정렬이 된다. 

 

코드 설명

 

전체적인 코드를 설명하자면 정렬된 튜플들은 끝나는 시간이 작은 것 부터 순회를 한다.

(1, 4) 의 start_time  = 1이고 et = 0 이니 

end_time = et = 4 가 되고 회의실 배정이 됐으므로 cnt += 1을 해준다

 

다음으로 (3, 5) 와 (0, 6) 은 start_time 이 3과 0 이므로 그냥 pass해준다

그 다음 (5, 7) 은 start_time 이 5이고 et가 4 이였으므로

end_time = et = 7 이 되고 회의실 배정이 됐으므로 cnt += 1을 해준다.

 

계속 끝까지 알고리즘을 반복하다보면

저렇게 노란색 부분 처럼 회의실 배정이 되는 효율적인 알고리즘을 만들 수 있다.