[백준] 1931번 회의실 배정 - 결과 포함

www.acmicpc.net/problem/1931

1931번: 회의실 배정

회의의 수 N과 N만큼의 회의 정보(회의 시작 시간, 종료 시간)가 주어지면 최대한 많은 회의를 가지는 것이 목표이다.

특수한 경우는 시작과 종료가 같은 경우도 존재한다는 것이었다.

 

가장 먼저 든 생각은 종료 시간이 빨라야 더 많은 스케줄을 채울 수 있다는 것이었다.

시작 시간이 아무리 빨라도 종료 시간이 크면 그 만큼 할 수 있는 회의도 줄어들었다.

 

입력이 무작위로 주어지기 때문에 일단 정렬을 해야했다.

파이썬 정렬은 신기했다.

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

람다를 이용해서 함수 안에서 원하는 정렬 조건을 줄 수 있었다.

위의 코드는 2차원 리스트에서 list의 원소 안에 있는 두 원소 중 두 번째 원소를 기준으로 오름차순 정렬하고 만약 같을 경우 두 번째 원소를 이용해 정렬하는 것이다.

예를 들어,

list = [[1,4],[1,3],[3,5],[5,3]]

이런 이중리스트가 존재한다면

list = [[1,3],[5,3],[1,4],[3,5]]

이렇게 정렬이 된다.

 

종료 시간이 가장 빠른 것부터 시작해야 하므로 위와 같은 조건으로 정렬했다.

처음에는 하나의 회의에 접근할 때마다 해당 회의가 끝난 후 수행할 수 있는 회의 리스트를 새로 만들어 갱신하는 방법을 생각했다.

그러나 남은 회의 리스트 자체가 전체 회의 리스트에서 나오기 때문에 만약 시작 시간과 종료 시간이 같을 경우

계속 갱신되서 무한루프에 빠지는 문제가 발생했다.

 

계속 시도하다가 처음부터 다시 생각하기로 결심했다.

다시 처음부터 생각하니 너무 어렵게 생각하고 있었다.

굳이 남은 일정을 체크할 필요없이 현재 종료시간을 기준으로 다음 시작시간을 찾으면 되는 문제였다.

 

코드도 훨씬 짧아지고 시간 초과도 해결했다.

이전의 코드는 O(n^2)였지만 O(n)으로 줄어들었다.

 

그리디 알고리즘에 대해 깨달았던 문제였다.

너무 어렵게 생각하고 미래의 경우의 수에 대해 많은 고민을 하다보니

이미 생각을 하지 않아도 되는 문제들을 복합적으로 생각하고 있었다.

 

코딩테스트에서 그리디 알고리즘 문제가 나오면 그리디 알고리즘 문제라는 것을 이제 어느 정도 파악할 수 있을 것 같다.

 

[전체 소스 코드]

n = int(input())
time = list()
result = 0

for i in range(n):
    data = list(map(int, input().split()))
    time.append(data)

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

curEnd = -1
for i in range(n):
    if time[i][0] == time[i][1]:
        result += 1
        curEnd = time[i][1]
    elif curEnd <= time[i][0]:
        result += 1
        curEnd = time[i][1]

print(result)