[백준 1931번 회의실배정] 문제 해설 - 파이썬

[백준 1931번 회의실배정] 문제 해설 - 파이썬

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의들에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 2^31-1보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 최대 사용할 수 있는 회의 수를 출력하여라.

---

문제 접근법

• 프로그래밍 콘테스트 챌린징 에도 수록된 유명한 문제입니다. 저는 이와 같은 문제를 16년 교내 프로그래밍 문제에서 만났습니다. 코알못 시절이라 엑셀에 테스트케이스를 정렬했던 기억이 납니다.
• 본 문제 해결을 위해서 그리디 알고리즘을 이용합니다.
• 본 문제의 핵심은 빨리 끝나는 회의 순서대로 정렬을 해야 합니다. 프로그래밍 콘테스트 챌린징에서도 증명을 하지 않고 넘어간 부분이여서 처음에는 이해하기 어려웠습니다. 다만 빨리 끝날수록 뒤에 올 수 있는 회의가 많다고 직관적으로 이해하면 됩니다.
• 따라서 현재 상황에서 최선의 선택(가장 회의가 빨리 끝나는)한다는 점에서 그리디 알고리즘이라고 할 수 있습니다.

주의 사항

• 다음 문제 조건에 유의해야합니다. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

• 다음 테스트 케이스에 대비해야합니다.

  2
  10 10
  1 10

• 만약 끝나는 시간만 정렬한다면 (10 10)이 선택된다면 (1 10)은 선택되지 못해서 결과는 1이 나올 것입니다.

• 시작 하는 시간의 오름 차순으로 정렬되야 (1 10) -> (10 10) 을 선택하여 2가 나올 것입니다.

따라서
(1) 끝나는 시간이 가장 빠른 순으로 정렬
(2) 시작하는 시간의 오름차순
조건으로 정렬해야합니다.

2개의 조건을 만족하기 위해서 sort를 2번 하는 방법이 있겠지만 다음과 같은 방법도 가능합니다.

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

위와 같이 key에 2개의 인자를 주면 인자의 순서대로 정렬을 합니다. 첫 번째로 x[1] 로 정렬을 하고 다음 x[0]으로 정렬합니다.

파이썬 코드

def solution(InputArr):
    answer = 0
    endTime = 0
    for i in range(len(InputArr)):
        if endTime <= InputArr[i][0]:
            endTime = InputArr[i][1]
            answer += 1
    return answer


N = int(input())
InputArr = []

for i in range(N):
    A, B = map(int, input().split())
    InputArr.append([A, B])

InputArr.sort(key=lambda x: (x[1], x[0]))
print(solution(InputArr))