[백준] 그리디 알고리즘 - 1931번: 회의실배정

회의실배정

풀이과정

1. meetings 리스트에 [[시작시간, 끝나는 시간], [시작시간, 끝나는 시간], ...]의 형태로 값을 입력 받는다.
2. meetings 리스트를 끝나는 시간 기준으로 정렬한다.
3. 끝나는 시간이 이른 회의부터 우선적으로 회의실에 배정한다. meetings의 원소들을 for문을 돌려 전 회의가 끝난 후 시작되는 회의 중 끝나는 시간이 가장 이른 회의가 회의실을 사용하도록한다.

Python Code

import sys

n = int(sys.stdin.readline().rstrip())
meetings = []
answer = 0
for i in range(n):
    meetings.append(list(map(int, sys.stdin.readline().rstrip().split())))

meetings.sort(key=lambda x: (x[1], x[0]))
finish = 0
for i in meetings:
    if i[0] >= finish:
        answer += 1
        finish = i[1]

print(answer)

오류와 해결

처음에 meetings 리스트를 시작시간을 기준으로 정렬한 후 이중 for문을 사용해서 한 회의가 끝난 후 가장 시작시간이 이른 회의를 다음에 배정하여 모든 경우의 수를 따져 최댓값을 구하도록 코드를 짰더니 시간복잡도가 O(N^2)이 되어 시간 초과가 발생했다.

meetings.sort(key=lambda x:x[0])

for i, v in enumerate(meetings):
    finish = v[1]
    temp = 1
    for j in range(i+1, len(meetings)):
        if meetings[j][0]>=finish:
            temp += 1
            finish = meetings[j][1]
    if answer < temp:
        answer = temp

그리디 방식을 이용하여 모든 경우를 따지지 않고 가장 빨리 끝나는 회의를 우선적으로 배정하도록 O(N)의 시간복잡도를 갖는 코드로 수정했다. 그랬더니 시간초과 문제는 해결되었지만 채점 마지막 즈음에 틀렸습니다가 떠버렸다. 질문글을 찾아보니 반례를 찾을 수 있었다.

meetings.sort(key=lambda x: x[1])

meetings를 끝나는 시간 기준으로 정렬할 때 그냥 두번째 원소를 기준으로 정렬하도록 했더니
2
2 2
1 2
의 경우에 오답이 나왔다. 1 2, 2 2의 순으로 회의가 가능하여 정답은 2지만 2 2만 가능하다고 판단하여 1이 결과로 나왔다. 1 2가 2 2보다 뒤에 입력되었기 때문에 두번째 원소를 기준으로 정렬하면 이미 2시에 회의가 끝난 시점에 1 2의 경우를 판단하기 때문이다.

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

meetings를 두번째 원소를 기준으로 우선 정렬하고 그 값이 동일하면 첫번째 원소를 기준으로 다시 정렬하도록 수정했더니 문제가 해결되었다.