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

🤒 문제

BOJ-1931 회의실 배정

💊 풀이

그리디 알고리즘 문제이다. 미리 정한 기준에 따라 순간 순간 가장 최선의 선택을 따라가는 것이다. 이 문제의 핵심은 회의가 끝나는 시간 이다.

• 간단하게 생각하면, 회의가 일찍 끝날수록, 후에 더 많은 회의를 할 수 있다.
• 따라서 끝나는 시간이 빠른 순으로 정렬한다.
• 또, 같은 시간에 끝나는 회의라면 회의가 빨리 시작하는 순으로 정렬해야 한다.
  • 그 이유는 아래에 정리 되어 있다.

🎈 회의가 끝나는 시간이 같은 경우

• 예를들어 (7, 7) (3, 7) 두 번의 회의를 정렬하지 않고 그리디 알고리즘으로 회의실을 배정해보자.
  • 만약 (7, 7) 회의가 내가 소스코드에서 정의한 조건인 시작시간이 end보다 느리거나 같을 경우 채택 의 조건에 부합하여 채택되었고 count는 1 증가했다고 가정한다.
  • 원래대로라면 (3, 7) 도 채택 되어야 하지만, 내가 설정한 조건과 맞지 않아 무시된다. 시작 시간이 end보다 느리기 때문이다.
• 시작시간이 빠른 순으로 정렬하고 한다면 -> (3, 7) (7, 7)
  • 두 번의 회의가 모두 채택된다.

deque를 사용하는 이유

그냥 리스트를 사용한다면 정렬할때 내림차순으로 정렬하거나, pop(0)으로 리스트에서 제거 해야 한다.

내림차순으로 정렬하는것은 문제 풀때 헷갈리고, pop(0)은 시간 복잡도가 O(n)으로 좋지 않다. 따라서 deque모듈의 popleft()를 사용하는 것이다. popleft는 시간 복잡도가 O(1) 이다.

정렬

sort()나 sorted() 를 사용하는데, 이때 람다함수로 기준을 주는것이 편하다. 튜플을 key로 넘기면 0번째 원소가 첫번째 기준, 1번째 원소가 두번째 기준이 되어 오름차순(default)로 정렬된다.

✨ 소스코드

import sys
from collections import deque

N = int(input())
times = []
for _ in range(N):
    time = tuple(map(int,sys.stdin.readline().split()))
    times.append(time)

# 회의가 빨리 끝나는 순서대로 정렬
# 두번째 기준은 회의 시작시간
times.sort(key= lambda x: (x[1], x[0]))
times = deque(times) # 덱에 담기 # 효율: popleft > pop(0)

count = 1
end = times[0][1]
times.popleft() # 가장 빨리 끝나는 회의 선택

while(times):
    # 시작시간이 end보다 느라거나 같을 경우 채택
    if times[0][0] >= end:
        end = times[0][1]
        times.popleft()
        count += 1
    else:
        times.popleft()

print(count)