백준 문제풀이 - 1931 번

링크 -> https://www.acmicpc.net/problem/1931

1. 요약 및 풀이방법

그리디 알고리즘의 대표적인 문제인 회의실 사용표 만들기 문제입니다.

현재 상황에서 최선의 선택을 하는 그리디 알고리즘에 맞게
회의 시간표를 오름차순으로 정렬하고,
최대한 빨리 끝나는 회의를 선택,
그리고 그 다음 회의는 이전의 회의보다 늦게 시작하면서, 동시에 최대한 빨리 끝나는 회의.
위와 같은 직관적인 논리에 따라 풀이하였습니다.

2. Code

from functools import cmp_to_key

def compare(x, y):
    if x[1] < y[1]:
        return -1
    elif x[1] > y[1]:
        return 1
    else:
        if x[0] < y[0]:
            return -1
        elif x[0] == y[0]:
            return 0
        else:
            return 1

def input_values():
    N = int(input())
    if N < 1 or N > 100000:
        raise ValueError()

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

    return meeting_times

def main():
    meeting_times = input_values()
    meeting_times.sort(key=cmp_to_key(compare))

    count = 0
    for times in meeting_times:
        if count == 0 or times[0] >= last[1]:
            last = times
            count += 1

    print(count)

if __name__ == "__main__":
    main()

3. 학습 내용

처음에는 meeting_times를 정렬할 때,
meeting_times.sort(key=lambda times: times[1])
와 같이 끝나는 시간을 기준으로 정렬하였습니다.
하지만 이 경우,

2
1 1
0 1

>>> output: 1
>>> 정답: 2

위와 같이 동시에 시작하고 끝나는 회의에 대한 처리가 불가능 했습니다.
이를 해결하기 위해 끝나는 시간을 기준으로 정렬하되,
끝나는 시간이 동일한 경우, 시작 시간을 기준으로 정렬 해야합니다.

functools의 cmp_to_key를 이용하여 정렬을 커스터마이징 했습니다.
cmp_to_key에 들어가는 compare 함수는,
두 인자를 받아서
전자가 앞으로 정렬되는 경우 -1,
후자가 앞으로 정렬되는 경우 1,
정렬이 필요없는 관계인 경우 0을 리턴합니다.

4. 결과