Problem
https://www.acmicpc.net/problem/1931
Solution
※ 풀이 포인트 끝나는 시간 기준으로 정렬하기
이 문제에서 중요한 점은 6 6과 같은 회의 직후에 6 7이 올 수 있다는 것이다.
오답코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
n = int(input())
time = list()
for i in range(n):
time.append(list(map(int, input().split()))) # 입력값을 2차원 리스트로 저장
time.sort(key=lambda x:x[1]) # 안쪽 리스트의 1번 인덱스 값을 기준으로 정렬
present = 0
count = 0
for i in time:
if i[0] >= present:
present = i[1]
count += 1
print(count)
위 코드는 아래와 같은 반례가 존재한다.
1
2
3
4
5
6
7
5
6 7
6 6
5 6
5 5
7 7
위와 같이 입력했을 때 정답인 5가 아닌 4가 출력된다.
1
2
3
4
5
6
5
6 7
5 6
6 6
5 5
7 7
위와 같이 3, 4번째 줄을 바꿔서 입력하니 제대로 출력되는 것으로 보아 이차원 리스트를 정렬할 때 [5,6]보다 [6,6]이 앞에 오게 되어 발생하는 문제로 보인다.
정답코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import sys
n = int(sys.stdin.readline())
time = list()
for i in range(n):
time.append(list(map(int, sys.stdin.readline().split())))
time.sort(key = lambda x : (x[1], x[0]))
present = 0
count = 0
for i in time:
if i[0] >= present: # 현재 회의의 끝시간과 같거나 늦는 경우
present = i[1]
count += 1
print(count)
위의 코드에서 리스트를 정렬할 때 time.sort(key = lambda x : (x[1], x[0]))과 같이 작성하였는데, 안쪽 리스트의 1번 인덱스를 기준으로 정렬하되, 같은 값이 나오면 0번 인덱스를 통해 정렬하는 방식이다.
여담으로 처음에는 위 코드에서 입력받는 부분을 전부 input()을 사용하였는데 채점시간이 4480ms가 나와서 sys.stdin.readline()으로 바꿔주니 344ms로 10배가 넘게 빠르게 나왔다. 채점에서 입력되는 n값이 상당히 큰 것 같다.