👩🏻💻 문제
👩🏻💻 정답 코드
n = int(input())
room = []
for i in range(n):
a, b = map(int, input().split())
room.append([a, b])
room.sort(key = lambda x: x[0])
room.sort(key = lambda x: x[1])
count = 1
end = room[0][1]
for i in range(1, n):
if room[i][0] >= end:
count += 1
end = room[i][1]
print(count)처음에는 start=[], end=[], time=[]으로 다 따로 리스트로 받아서 time이 최소인 인덱스부터 시간을 채우는 걸로 생각하다가 감이 안 와서... 이분 풀이를 참고했다.
종료 시간이 빠르면 다른 회의가 시작할 기회가 생기므로 먼저 채택하는 것이 좋다. 그래서 입력을 room에 이중 배열로 받은 후에 종료 시간을 key로 해서 정렬하면 되는 것이라고 생각했다. 근데 한 가지 더 고려해야 할 점이 있었다. "종료 시간이 같은 경우"였다.
문제를 보면 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.라는 말이 있다.
(2, 3) 과 (3, 3)의 회의 시간이 주어졌을 때는 두 가지 경우가 있다.
(2, 3)을 먼저 진행 ->(3, 3)진행 가능(3, 3)을 먼저 진행 ->(2, 3)진행 불가
따라서 "종료 시간이 같은 경우"에는 시작 시간이 이른 회의를 진행해야 한다. 따라서 정렬 부분의 코드를 아래와 같이 짜야 하는 것이다.
room.sort(key = lambda x: x[0]) # 시작 시간을 기준으로 정렬
room.sort(key = lambda x: x[1]) # 종료 시간을 기준으로 정렬그 이후에는 end 변수에 종료 시간을 기록해 두면서 그 이후의 회의만 가능하므로 room[i][0] >= end인 경우에 count를 올리고 새로운 종료 시간인 room[i][1]으로 end를 바꿔 준다.
👩🏻💻 Remember
arr.sort(key = lambda x: x[0])이중 배열에서 내부 배열의 index가 0인 값들을 기준(key)으로 전체 배열 정렬
wanderlust