Python으로 푸는 백준 1931. 회의실배정

백준 1931. 회의실배정

 문제는 삼성 SW Expert에 5202. 화물 도크 문제와 유사하지만

좀더 까다로운 문제라고 할 수 있다.

시작하자마자 종료되는 회의가 존재하기 때문이다.

회의실 사용표를 보고 최대 사용할 수 있는 회의수를 출력해야 한다.

이 문제를 해결하려면 어떻게 해야 할까.

문제 보러 가기

github에서 코드 보기

문제에서 제시한 조건

- 회의는 한번 시작하면 종료할 수 없다.

- 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다.

- 회의의 시작 시간과 끝나는 시간이 같을 수도 있다. (시작하자 마자 끝나는 회의로 보면 된다.)

문제 풀기 전 결정 사항

- 내부적으로 파이썬에 내장되어 있는 sort 함수의 시간 복잡도는 평균적으로 nLogn이므로 별도의 정렬 메소드를 다시 짤 필요는 없다.

(보통 개발자가 짠 것보다 내장 정렬 함수가 더 효율적이다. 파이썬 언어 자체의 속도보다도 최적의 알고리즘과 자료구조를 사용하지 않았을 가능성이 훨씬 크다.)

문제 풀이 방법

- 기존에 정렬이 된 리스트를 파이썬 내부 정렬 함수를 이용해 다른 기준으로 재정렬을 한다면, 기존 기준의 결과값을 최대한 유지하면서 정렬되도록 한다.

- 이 문제에서는 시작시간과 종료 시간이 일치하더라도 회의실 배정이 가능하다는 조건이 있다. 즉, (1, 2), (2, 2) 는 모두 회의실을 배정 가능하다는 말이다

- 이 문제를 해결하기 위해선, 시작 시간 기준으로 정렬하고, 다시한번 종료 시간을 기준으로 재정렬을 해야만 한다.

- 회의실배정 문제에서 다음의 예시를 배정해보았을 경우 다음과 같다.

5
1 4
3 5
3 4
2 2
1 2

case 1. 시작 시간 기준으로 정렬 후, 종료 시간 기준으로 재정렬
# 시작 시간 기준으로 정렬
[(1, 4), (1, 2), (2, 2), (3, 5), (3, 4)]
# 종료 시간 기준으로 정렬
[(1, 2), (2, 2), (1, 4), (3, 4), (3, 5)]


case 2. 종료 시간 기준으로만 정렬
# 종료 시간 기준으로만 정렬
[(2, 2), (1, 2), (1, 4), (3, 4), (3, 5)]

코드 상, (2,2)를 먼저 배정할 경우, (1,2)가 배정되지 않아 결과값이 잘못 나올 수도 있다.
그러므로 시작 시간 기준으로 정렬 한 후, 종료 시간 기준으로 재정렬한다면 
기존의 시작 시간 기준으로 정렬한 값들을 최대한 유지하려 하기 때문에
종료 시간이 같다면, 시작 시간이 빠른 기준으로 정렬된 결과물을 받아 볼 수 있다.

위 input 값을 어떻게 정렬 했느냐에 따라서 결과 값은 다르게 나온다.

# case 1 : 3 (o)
# case 2 : 2 (x)

코드 리뷰

파이썬 내장 함수의 효율로 인해서 코드가 잘 돌아가지 않는 경우는 드물다.

시간 초과가 났다면 내장 함수(여기선 정렬)에 의문을 가지지 말고 우선적으로 코드를 고쳐보려고 노력해야 한다.

내 코드가 잘못됐을 확률이 가장 높다.

파이썬 코드

import sys
 
def greedy(meeting):
    meeting_count = 0
    start_time = 0
 
    for time in meeting:
        if  time[0] >= start_time:
            start_time = time[1]
            meeting_count += 1
    return meeting_count
 
 
if __name__=="__main__":
    mCount = int(sys.stdin.readline())
    meeting = []
    for i in range(mCount):
        start, end = map(int, sys.stdin.readline().split())
        meeting.append((start, end))
    # 시작 시간 기준으로 정렬
    meeting = sorted(meeting, key=lambda time: time[0])
    # 종료 시간 기준으로 정렬
    meeting = sorted(meeting, key=lambda time: time[1])
    print(greedy(meeting))

#5202. 화물 도크 #1931 회의실 배정 #1931 회의실 배정 python #1931 회의실 배정 파이썬 #파이썬 1931 회의실 배정 #python 1931 회의실 배정 #백준 회의실 배정 #회의실 배정 백준 #회의실배정 백준 #python 회의실 배정 #화물 도크 유사문제 #백준 5202 #백준 화물도크 #화물도크 백준 #백준 화물 도크 #화물 도크 백준