[Python/파이썬] 백준 알고리즘 1931 - 회의실 배정 (Greedy Approach)

 

 

 

<풀이>

처음 필자는 시작 시간과 끝나는 시간의 차를 구해 그것을 기준으로 오름차순 정렬 후 다른 회의 시간대와 겹치지 않는다면 추가하는 방식으로 풀려고 했다.

하지만 이 방식의 경우 이중 for문을 사용하게 되므로 O(n^2) : 100000 * 100000 = 100억 (> 4억(시간제한 2초))이 되버려 불가능한 풀이였다.

 

이는 조금 생각을 달리하여 풀리는 문제였는데, 전체 회의의 시작시간은 0시로 정해져있으니 굳이 회의 시간을 구해주지 않더라도 끝나는 시간을 기준으로 오름차순 정렬하면 그것이 회의 시간을 정렬한 것과 비슷한 의미가 될 수 있었다.

 

그리고 한가지 더 고려해야할 사항이 있는데 끝나는 시간이 같은 경우이다.

끝나는 시간이 같다면 빨리 시작하는 순서대로 정렬이 되어야한다.

예를 들어보겠다.

(3 3), (1 3)

과 같이 정렬되어있다고 하면 (1 3)은 (3 3)의 끝나는 시간보다 시작 시간이 앞에있기 때문에 무시되고 총 가능 회의 수는 1번이 된다.

 

이를 해결하기 위해 끝나는 시간을 오름차순으로 정렬해준 뒤, 시작하는 시간도 오름차순 정렬해줘야한다.

 

즉, 1. 끝나는 시간 오름차순 2. 시작하는 시간 오름차순 으로 정렬해줘야한다.

 

아래는 소스 코드이다.

"""
1. 아이디어
끝나는 시간을 기준으로 오름차순 정렬하고 그 다음 시작하는 시간을 기준으로 오름차순 정렬한다.
그리고 for문으로 돌려 앞전의 끝나는 시간과 현재 for문으로 들어온 회의의 시작 시간을 비교해 겹치지 않는다면
가져와 전체 회의 끝나는 시간을 현재 for문으로 들어온 회의의 끝나는 시간으로 바꾼다.

2. 시간복잡도
- O(nlgn) : 100000 * 16.6 = 1660000 < 4억    -> 가능

3. 자료구조
N: int;
info: int[][];
curEndTime: int;
maxCnt: int;
"""
import sys

input = sys.stdin.readline

N = int(input())
info = [list(map(int, input().split())) for _ in range(N)]

info.sort(key=lambda x: (x[1], x[0]))

maxCnt = 0
curEndTime = 0
for start, end in info:
    if curEndTime <= start:
        curEndTime = end
        maxCnt += 1


print(maxCnt)

sort할 때 key에 튜플로 여러 인자를 주면 해당 인자의 순서대로 기준을 잡고 정렬해준다.

 

 

 

<핵심 정리>

1. 파이썬에서 sort 함수를 쓸 때 key=lambda x:x[]를 파라매터로 넣어주면 해당 기준에 따라 정렬할 수 있다.

2. 그리디 문제를 풀 때는 무엇을 기준으로 먼저 선택할지를 고민하는 것이 가장 중요하다