Softeer Level 3 강의실 배정 Python [반례 포함]

문제 링크

https://softeer.ai/practice/6291

Softeer - 현대자동차그룹 SW인재확보플랫폼

정답 코드

import sys
input = sys.stdin.readline
N = int(input().strip())
classes = sorted([list(map(int, input().split())) for _ in range(N)], key=lambda x: (x[1], x[0]))
maxCnt = 1
nowEnd = classes[0][1]
for i in range(1, N):
  next = classes[i]
  if nowEnd <= next[0]:
    nowEnd = next[1]
    maxCnt += 1
print(maxCnt)

풀이 방법

- 처음 강의 시간을 정렬해서 받아야 합니다.

- 여기서 정렬은 강의 시간의 끝나는 시각을 기준으로 오름차순 정렬한 다음

- 겅의 시간의 시작하는 시각을 기준으로 오름차순 정렬합니다.

- 정렬 이후에는 이제 가장 앞에 있는 강의시간을 기준으로 끝나는 시간을 비교해주면서 계산하면 됩니다.

    - next[0]은 다음 강의시간의 시작시간입니다.

반례

6
1 2
2 10
2 3
3 5
3 4
4 10

6
1 2
2 3
3 8
4 5
5 6
5 10

6
1 10
1 4
2 5
3 6
4 8
3 4

3
1 100
2 3
3 4

2
2 10
2 10

1
1 2

3
2 4
4 5
99 100

느낀점

- 전에 백준이나 SWEA에서 강의실 배정하는 문제를 풀어봤지만 오랜만에 풀어보니 조금 오래 걸렸다.

- 람다식과 그리디 알고리즘을 다시 공부해야겠다.