[goormlevel] 구름스퀘어

문제

구름스퀘어의 타운 홀은 다양한 행사를 진행할 수 있는 공간이다. 타운 홀에 N개의 행사가 예정되어 있다. i번째 행사는 시작 시간 $s_{i}$와 종료시간 $e_{i}$까지 진행하려고 하고, 행사끼리 진행하는 시간이 서로 겹치지 않게 가장 많은 행사를 여는 것이 목표이다.
행사는 한 번 시작하면 중간에 종료할 수 없다. 그리고 행사가 종료된 후 바로 다음 행사를 진행할 수는 없고, 최소 1의 시간이 지난 뒤에 다른 행사가 시작할 수 있다. 행사의 시작 시간과 종료 시간이 동일한 경우도 있으며, 이는 시작하자마자 종료된 행사라고 할 수 있다.
타운 홀에서 열릴 수 있는 행사의 최대 개수를 출력하시오.

입력

첫째 줄에 행사의 개수 N이 주어진다.
다음 N개의 줄에는 i번쨰 행사의 시작 시간과 끝 시간을 나타내는 $s_{i}$, $e_{i}$가 공백을 두고 주어진다.

• 1 $\leq$ N $\leq$ 200 000
• 1 $\leq$ $s_{i}$ $\leq$ $e_{i}$ $\leq$ $10^9$

입력에서 주어지는 수는 모두 정수이다.
타운 홀에서 열 수 있는 행사의 최대 개수를 출력하시오.

내 풀이

input1 = input()

eventlist = []
for i in range(int(input1)):
	eventlist.append(input())

eventlist1 = []
for i in eventlist:
	a = list(map(int, i.split()))
	eventlist1.append(a)
	
eventlist1.sort(key=lambda x:(x[1], x[0]))

count = 0
last_end_time = -1
for a in eventlist1:
	if a[0] > last_end_time:
		count += 1
		last_end_time = a[1]
		
print(count)

코멘트

이번 문제도 정렬에서 꼬여서 다른 풀이를 찾아보게 되었다. 나는 처음에 i번째 행사의 종료 시간과 (i+1)번째 행사의 시작 시간 사이의 차이를 기준으로 정렬해야 한다고 생각했는데, 다른 풀이들을 보니 행사들의 종료 시간을 기준으로 정렬하고 있었다. (종료 시간이 같으면 시작 시간 기준으로 정렬)
그리고 선택된 행사 수를 저장할 count를 선언하고, last_end_time이라는 변수를 설정해서 ($\rarr$ 이전 행사의 종료 시간) 이것보다 다음 행사의 시작 시간이 더 크면 가능한 행사의 수를 센다. (count+1) 초기에는 last_end_time = -1을 선언해서 첫 번째 행사가 항상 선택되게 한다. count를 올리고 나면 last_end_time을 이번 행사의 종료시간으로 업데이트 하는 식으로 하면 가능한 최대 행사 수를 셀 수 있다.

References

https://level.goorm.io/
https://velog.io/@hans1997/%EA%B5%AC%EB%A6%84LEVEL-%EA%B5%AC%EB%A6%84-%EC%8A%A4%ED%80%98%EC%96%B4-JS
https://hye-ding.tistory.com/97