[Baekjoon, Python] 1931번 : 회의실 배정

도입

백준 단계별 풀기 그리디 알고리즘 두 번째 문제이다.

백준 1931번 문제, 입력, 출력

---

백준 1931번 입출력 예제 1

---

그리디 알고리즘

 그리디 알고리즘(탐욕 알고리즘)이란, 문제를 해결하는 과정에서 그 순간순간마다 최적이라고 생각되는 결정을 하는 방식으로 진행하여 최종 해답에 도달하는 문제 해결 방식이다. 

 

 특징 - 1. 최적성의 원리 : 주어진 문제에 대한 최적해가 분할된 부분 문제의 최적해로 구성된다는 원리.

        - 2. 최적 해 보장 불가 

        - 3. 효율성 개선

 

그리디 알고리즘 예시 : 거스름돈 최소 동전 수

그리디 알고리즘 수행절차

 1. 해 선택 : 부분 해 집합에 추가 다음 항목 선택

                현재 상태 최적화 기준 만족 여부 확인

 2. 적합성 검증 : 새로운 부분 해 집합 조건 여부 확인

                      현재 집합이 해가 될 가능성 검사

 3. 해 검증 : 신규 구성 집합이 해인지 검사

                문제가 아니면 1번으로 돌아가서 반복

---

풀이

1. 가장 많은 회의 수를 알기 위해서는 끝나는 시간을 기준으로 오름차순 정렬을 먼저 해야한다. 동의 하는가? 빨리 끝날수록 뒤에 올 수 있는 회의가 많기 때문이다. 

 

2. 1.에 의해 정렬된 배열( [(1,4),(3,5), ... ,(2,13),(12,14)] )에서 그 다음은 시작하는 시간을 기준으로 오름차순 정렬을 해야한다. 문제의 조건에도 있듯이 (4,4)와 같이 시작시간 4, 끝나는시간 4인 경우, 1개의 회의로 카운트하기 때문이다. (3,4),(4,4)로 정렬해야 2개로 카운트가 된다. 

 

3. sorted 함수를 사용할 것이다. python.org의 문서를 참고해보면, 다중 수준의 정렬을 허용한다고 나와있다. 이것을 sorted함수 내의 key함수에 적용을 시켜보았는데, 정상적으로 잘 작동하였다. 

해당 문서를 참고하여, list_meeting을 x[1]=끝나는시간 으로 오름차순 정렬을 한뒤, x[0]=시작시간 으로 오름차순 정렬을 한다. 참고로 내림차순은 앞에 -(음수) 부호를 붙이면 된다.

4. 이렇게 정렬된 list_meeting을 for문을 돌려, 끝나는시간(end)보다 시작시간(i)가 클시, 회의 개수(rtn)을 하나 증가시키고, 해당 회의의 끝나는 시간(j)을 다음에 비교할 끝나는 시간(end)에 업데이트 한다.

---

코드

from sys import stdin

var_N = int(stdin.readline())
list_meeting = []

for _ in range(var_N):
    var_start, var_end = map(int, stdin.readline().split())
    list_meeting.append([var_start,var_end])

list_meeting = sorted(list_meeting, key = lambda x : (x[1], x[0]))

rtn = end = 0
for i,j in list_meeting:
    if i >= end:
        rtn += 1
        end = j

print(rtn)

---

마무리

생각이 필요한 문제, sorted에 다중 기준이 적용될 수 있는지 알게된 좋은 알고리즘이였다.