1931 회의실 배정

1. 문제

문제는 링크에 들어가면 있다.

2. 정답 코드

문제의 내 정답 코드는 다음과 같다.

import sys
read = sys.stdin.readline

N = int(read())
time_array = []
for i in range(N):
    time_array.append(list(map(int,read().split())))

# 회의가 빨리 끝나는 순대로 정렬하자. 그래서 제일 빨리 끝나는 것을 시작으로 다음 타임에 바로 올 수 있는걸 가져오는거지.
# print(time_array)
time_array.sort(key = lambda x: x[0])
# print(time_array)
time_array.sort(key=lambda x: x[1])
# print(time_array)
count = 1
end = time_array[0][1]
for j in range(1,N):
    if time_array[j][0] >= end :
        count +=1
        end = time_array[j][1]

print(count)

3. 문제 풀이

이 문제는 아이디어를 내는 것이 꽤나 어려웠다. 어떻게 하면 풀 수 있을지 고민하다가 결국 시간 제한에 의해 풀지 못하고 인터넷 풀이를 참고하게 되었는데, 핵심은 시작 시간이 빠른 것을 나열하는 것이 중요한 것이 아니다. 끝나는 시간을 나열해서 빨리 끝나는 시간끼리 계속해서 붙여나가는 것이 더 많은 시간표로 넣을 수 있는 것이다.

예를 들면, [1 5] [2 3] [3 4] [5 5] 가 있다고 해보자. 그러면 가장 빠른 시작시각은 [1 5]인데 이걸 쓰게되면 [1 5] [5 5] 만 쓰게 된다. 하지만 가장 빨리 끝나는 시간들을 나열해서 조건에 만족하는 것을 찾으면 [2 3] [3 4] [5 5] 가 된다. 스케쥴이 하나 더 많은 것이다. 따라서 끝나는 시간을 나열해서 위 코드의 조건처럼 나열을 시도하면 된다.

sort() 문법

그러나, 여기서 하나 깨달은 것이 있는데, sort()문법이다. sort()는 안에 key요소를 쓸 수 있는데, key=lambda x:조건 에 의해 해당 array가 배열되는 형식이다. 자세한 설명은 구글링을 참고하면 좋을 것 같고, 알게된 핵심은 list의 요소가 2개일 때, 앞요소끼리 먼저 배열을 한 후, 뒷 요소끼리 배열을 다시 해주어야 한다는 것이다.

뒷요소만 정렬을 하게되면 다음과 같은 list의 변화가 일어난다.

원본 : [[1, 4], [3, 5], [0, 6], [8, 9], [5, 7], [3, 8], [5, 9], [6, 10], [8, 11], [8, 12], [6, 9], [2, 13], [12, 14]]

뒷요소만 : [[1, 4], [3, 5], [0, 6], [5, 7], [3, 8], [8, 9], [5, 9], [6, 9], [6, 10], [8, 11], [8, 12], [2, 13], [12, 14]]

보면 [8,9], [5,9], [6,9] 순으로 정렬됨을 볼 수 있는데, 이렇게 되면 하나씩 훑는 그리디 과정에서 문제가 발생할 수 있다. 이렇게 되는 요인은 아마도 sort(key=lambda x:x[1])을 할 때, 조건에 맞는 요소를 앞에서부터 차례대로 찾게 되어서 발생하는 것 같다. 그래서 먼저 x[0]에 따라서 앞 요소끼리 정렬을 한번 한 후, x[1]에 따른 뒷 요소끼리 정렬을 하게 되면 결과는 다음과 같이 변한다.

원본 : [[1, 4], [3, 5], [0, 6], [8, 9], [5, 7], [3, 8], [5, 9], [6, 10], [8, 11], [8, 12], [6, 9], [2, 13], [12, 14]]
앞 요소 먼저 : [[0, 6], [1, 4], [2, 13], [3, 5], [3, 8], [5, 7], [5, 9], [6, 10], [6, 9], [8, 9], [8, 11], [8, 12], [12, 14]]
뒷 요소 먼저 : [[1, 4], [3, 5], [0, 6], [5, 7], [3, 8], [5, 9], [6, 9], [8, 9], [6, 10], [8, 11], [8, 12], [2, 13], [12, 14]]

그러면 깔끔하게 정렬되는 것을 볼 수 있다.

여담으로 sort(key=lambda x:(x[0],x[1]))로 한번에 코드를 만들 수 있을 거 같은데, 이걸 사용하게되면 백준사이트에서 정답이 틀렸다고 한다. 왜그런진 모르겠다..