백준 1931 파이썬

1931번: 회의실 배정

 

 

정답 코드

from sys import stdin
import heapq

read = stdin.readline

N = int(read())
heap = []
result = []
for _ in range(N):
    a, b = map(int, read().split())
    result.append((a, b))
result = sorted(result, key=lambda x: x[0])
result = sorted(result, key=lambda x: x[1])

count, last = 0, 0
for start, end in result:
    if start >= last:
        count += 1
        last = end
print(count)

1. 시작 시간을 기준으로 먼저 정렬한다.

그렇게 되면 먼저 시작하는 강의 부터 정렬된다. 끝나는 시간은 보장되지 못한다.

 

2. 끝나는 시간을 기준으로 다시 정렬한다.

그렇게 되면 이미 시작 시간을 기준으로 정렬이 된 상태에서, 다시 끝나는 시간으로 정렬된다.

만약 예시로 (4, 4) 와 (1, 4) 가 있다면, 시작 시간을 기준으로 먼저 정렬을 해야, 문제에 의도대로 정렬할 수 있게 된다.

 

오답 코드

소팅 과정에서 람다를 이용했다.

처음에는 람다식으로 시작 시간과 종료 시간을 동시에 정렬하려고 했다.

result = sorted(result, key=lambda x: (x[0], x[1]))  # 위의 두 라인과 이 라인은 엄연히 다르다.

 위 코드의 문제는 시작 시간과 종료 시간을 모두 기준으로 정렬한다는 점이다. (사실 첫번째 원소로만 정렬된다.)

 

from sys import stdin
import heapq

read = stdin.readline

N = int(read())
heap = []
result = []
for _ in range(N):
    a, b = map(int, read().split())
    result.append((a, b))
result = sorted(result, key=lambda x: (x[0], x[1])) 위의 두 라인과 이 라인은 엄연히 다르다.

count, last = 0, 0
for start, end in result:
    if start >= last:
        count += 1
        last = end
print(count)