문제
한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.
입력
첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.
출력
첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.
N = int(input())
meeting_time = []
for i in range(N):
S,E = map(int,input().split())
meeting_time.append((S,E))
meeting_time.sort(key = lambda x : (x[1],x[0]))
end = meeting_time[0][1]# 4
count = 1
for i in range(1,N):
if meeting_time[i][0]>=end:
end = meeting_time[i][1]
count += 1
print(count)
어려웠다..
일단 당연히 입력을 받아오는 부분은 문제 없이 구현 할 수 있었다.
그리고 정말 아무 생각 없이 meeting_time이라는 배열에 시작시간과 끝시간을 의미하는 S,E를 튜플 형태로 집어넣어 주었다.
그리고 막혔다...
그러다가 그리디 알고리즘으로 풀어야한다는 것을 사람들 블로그를 통해 확인하였고 그리디 알고리즘에 관한 유튜브 영상을 보던 중에 이 문제가 예시로 나왔고 어떻게 풀어야할지 힌트를 얻게 되었다.
회의의 시간들을 일단 끝나는 시간으로 정렬해 놓고 가장 먼저 끝나는 회의를 제일 먼저 진행한다면 가장 많은 회의를 진행할 수 있지 않을까라는 생각을 했다.
그렇게 하기 위해서는 meeting_time이라는 것을 끝나는 시간순으로 정렬을 해야했고 그때 사용한 코드가
meeting_time.sort(key = lambda x : (x[1],x[0]))이것이다.
이 코드를 사용하면 정렬을 하게 되는데 정렬의 우선순위는 먼저 x[1]을 기준으로 정렬하고 그 다음, x[1]값이 동일한 경우 x[0]을 기준으로 정렬하는 방식이다.
문제의 예제들이 이 코드를 통해 정렬된다면
meeting_time = [
(1, 4), # 시작 1, 종료 4
(3, 5), # 시작 3, 종료 5
(0, 6), # 시작 0, 종료 6
(5, 7), # 시작 5, 종료 7
(3, 8), # 시작 3, 종료 8
(5, 9), # 시작 5, 종료 9
(6, 10), # 시작 6, 종료 10
(8, 11), # 시작 8, 종료 11
(8, 12), # 시작 8, 종료 12
(2, 13), # 시작 2, 종료 13
(12, 14) # 시작 12, 종료 14
]이렇게 정렬이 되게 된다.
그러면 end = meeting_time[0][1]로 시작을 하면 가장 먼저 빨리 끝나는 회의를 제일 먼저 진행하게 되는 것이다. (최초의 end값은 4이다)
그 이후로
end = meeting_time[0][1]# 4
count = 1
for i in range(1,N):
if meeting_time[i][0]>=end:
end = meeting_time[i][1]
count += 1이 코드와 같이 반복문을 순회하면서 만약 미팅의 시작 시간이 기존의 end의 값보다 크다면 회의가 끝나면 바로 그 회의를 진행하면 되고 그때 새로운 회의의 끝나는 시간을 end에 계속 업데이트해주는 식으로 코드를 작성하였고 end가 업데이트 된다는 것은 새로운 회의가 시작한다는 뜻이므로 count를 1씩 올려주고 마지막에는 count를 출력해주면 정답이 나오게 된다.
