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

 

문제 요약

한 개의 회의실 - 이를 사용하고자 하는 N개의 회의

각 회의의 시작 시간, 끝나는 시간 주어질 때

겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수 구하기

-> 그리디의 대표적인 예인 Activity selection 문제이다.

-> 빨리 끝나는 시간 순으로 정렬하여 그리디로 풀 수 있다!

 

참고

https://en.wikipedia.org/wiki/Activity_selection_problem#:~:text=The%20activity%20selection%20problem%20is,finish%20time%20(fi).

Activity selection problem - Wikipedia

 

 

풀이

n = int(input())
meeting = [list(map(int, input().split())) for _ in range(n)]
meeting.sort(key=lambda x: (x[1], x[0]))

selected = [meeting[0]]
end_time = meeting[0][1]

for m in meeting[1:]:
    if m[0] >= end_time:
        selected.append(m)
        end_time = m[1]

print(len(selected))

 

 

기억할 점

정렬 기준 빠뜨리지 않기

lambda를 이용하여 정렬을 할 때, 시작시간을 기준으로 정렬하는 걸 빠뜨리면 틀린다.

meeting.sort(key=lambda x: (x[1])

아래와 같이 해야 함! 테스트 케이스를 꼼꼼히 생각해보자. 

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

 

반복문에서 리스트 슬라이싱

반복문에서 리스트 슬라이싱을 사용해서 코드를 간단히 만들 수 있다.

for m in meeting[1:]:

 

sort 이용하기

원본이 필요 없을 때, 리스트일 때는 sorted가 아닌 sort를 이용하면 된다.

성능은 거의 비슷하지만 추가 메모리 할당이 필요 없다는 이점이 있다.