백준 1931번 회의실배정 _ 탐욕알고리즘 (Greedy Algorithm) (python)

문제: https://www.acmicpc.net/problem/1931

1931번: 회의실배정

백준 1931번 탐욕 알고리즘

이번 1931번 문제는 정답률은 낮지만 탐욕알고리즘을 이미 알고 있었던 사람이라면, 정말 쉽게 접근이 가능했을 문제입니다.

탐욕 알고리즘이란? 모든 경우의 수를 생각하여 최선을 찾아내는 브루트포스나 동적계획법과는 달리 매 순간 순간의 선택에서 최선을 선택하는 알고리즘이라고 생각하면 되는데요.

이 문제의 경우 모든 회의 가능한 경우의 수 중 가장 많이 회의할 수 있는 경우를 찾는 형태가 브루트포스나 동적계획법의 형태라면,
그 때 그 때, 빨리 끝낼 수 있는 회의부터 끝내는 게 탐욕알고리즘이라고 할 수 있겠죠.
만약 이 문제에서 최소 회의시간 까지 고려하라고 했다면 탐욕 알고리즘을 통한 풀이가 불가능했을 겁니다. 하지만 그게 아니죠?

문제에서는 최대 가능한 회의의 수만을 물었기 때문에, 저희는 끝나는 시간을 모두 정렬한 후 일찍 끝나는 순서대로 회의를 진행한다면 아마도 가장 많은 회의를 할 수 있게 될 것입니다. 

한 가지! 여기에서 빠질 수 있는 함정은 바로 회의시작시간과 회의 끝 시간이 같다는 것인데요.. (이럴 수가 없지만.. 이게 가능하다고 문제가 가정하였기에 저희는 이것을 고려해주어야 합니다.)
예를 들어 회의 끝 시간만 고려한다면 1 3 이나 3 3 이나 원래 리스트에서 먼저 위치했던 회의가 먼저 처리되겠지만, 시작과 끝이 같을 수 있기 때문에 3 3 회의를 먼저 한다면 1 3 회의를 진행할 수 없지만 1 3 회의를 먼저 한다면 3 3 회의를 진행할 수 있겠죠?

때문에 저희는 회의가 끝나는 시간을 우선순위로 먼저 정렬해준 뒤에 그 순서 내에서 시작시간을 정렬해주어야 한답니다.

그럼 한번 코드를 보실까요?

num = int(input())
conf = [] // 문제에서 주어지는 회의들
Answer = [] // 최대로 많이 회의가 진행가능한 경우의 회의들이 저장될 리스트.

for _ in range(num):
    conf.append(list(map(int, input().split())))
    
// 끝나는 시간을 기준으로 정렬 후 그 안에서 시작시간을 기준으로 정렬.
conf = sorted(conf, key = lambda x:(x[1],x[0])) 

if num>0:
    Answer.append(conf[0]) 
    for i in range(1,num):
        if conf[i][0] >= Answer[-1][1]: //시작시간이 그 전 끝나는 시간보다 크거나 같다면 추가
            Answer.append(conf[i])

print(len(Answer))

 

끝!