[BOJ/Python] 19831 : 회의실 배정

👉 문제 링크

❌ 틀린 코드 ❌
이거 왜 아님? 왜 틀림?

import sys
input = sys.stdin.readline

n = int(input())
arr = []

for i in range(n):
    s,e = map(int,input().split())
    arr.append([s,e])

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

cnt, last = 0,0
for start,end in arr:
    if start >= last:
        cnt += 1
        last = end
       
print(cnt)

질문 게시판에서 회의 시작 시간과 종료 시간이 같은 경우를 고려해야 한다는 말을 보았다. 알고보니 문제에 써있었다....
그래서 위 코드에 시작 시간 기준으로 정렬하는 코드를 넣었는데 정답이란다. 그 코드를 넣지 않아도 같은 경우가 고려되지 않나? 했지만 답이 다르게 나왔다. 어디가 문제일까?

👉 해결 과정

반례를 찾았다. (3,3) (1,3) (3,3)을 넣으면 3이 나와야 하는데 2가 나온다. 정렬이 되지 않았다. 또한 (9,10) (10,10)과 같은 경우, (9,10)을 먼저 선택하면 (10,10)도 선택할 수 있지만 반대의 경우는 성립하지 않는다.
따라서 시작 시간 기준의 정렬이 필요하다.

하지만 고민이었던 것은

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

이렇게 하면 앞 정렬은 무시되는 거 아닌가? 였다.

반례를 같이 생각해보면 이해하기 쉽다!
(10,10) (9,10) 이 주어진 경우 시작 시간 순으로 정렬 하고 끝나는 순으로 다시 정렬을 한다면 (9,10) (10,10)이 되지만, 시작 시간 정렬이 없으면 (10,10) (9,10) 그대로인 것이다!
마찬가지로,
(3,3) (1,3) (3,3)의 경우에도 두 번의 정렬을 통해 (1,3) (3,3) (3,3)을 만들어야 한다!

👉 전체 코드

import sys
input = sys.stdin.readline

n = int(input())
arr = []

for i in range(n):
    s,e = map(int,input().split())
    arr.append([s,e])

arr.sort()
arr = sorted(arr, key=lambda x:x[1])

cnt, last = 0,0
for start,end in arr:
    if start >= last:
        cnt += 1
        last = end

print(cnt)

알고보면 별 거 아니였던 것.....
이러면서 하나 배운거지~