[Python] 백준(BOJ) - 1931 회의실배정

필자는 거의 항상 코딩 테스트, 혹은 알고리즘 문제 풀이를 파이썬으로 한다.

대체로 코딩 테스트는 C++로 하라고 하지만... 필자가 일하고자 하는 직무가 인공지능, 빅데이터 쪽이기도 하고,

C, C++은 임베디드 하면서도 자주 접하기 때문에 지식의 반경을 넓히고자 하는 욕심도 있기 때문이다.

 

이번 알고리즘 풀이 첫 문제는, 백준 온라인 저지의 1931번 문제 회의실 배정이다.

이 문제는 그리디 알고리즘의 대표격 문제이지만, 정답률은 28% 정도로 조금 낮은 편이다.

그 이유는 바로 끝나는 시간과 시작하는 시간이 겹칠 수 있다는 특수성 때문에 그럴 것이다.

 

지난 5567번 문제에서도 그랬지만 이 포스트에서 그리디 알고리즘에 대한 이론 설명은 하지 않겠다.

이는 따로 "이론 카테고리"에서 정리할 예정이다.

 

한 번 바로 살펴보자.

---

소스 코드

#BOJ 1931 회의실 배정

import sys
input = sys.stdin.readline

def greedy(meeting):
    cnt = 0
    start = 0
    for item in meeting:
        if item[0] >= start:
            start = item[1]
            cnt += 1
    return cnt

N = int(input())
meeting = []
for i in range(N):
    start, end = map(int, input().split())
    meeting.append((start, end))
meeting = sorted(meeting, key = lambda item:item[0])
meeting = sorted(meeting, key = lambda item:item[1])
print(greedy(meeting))

그리디 알고리즘을 익히기에 정말 좋은 문제가 아닐까 싶다.

참고로 meeting 리스트를 두 번 정렬한 것은, 우선적으로 시작 시각 기준으로 정렬한 후, 종료 시각 기준으로 정렬을 해야 올바르게 그리디 탐색을 할 수 있기 때문이다.

 

당연하지만 결과는,

아주 좋다.

맞았다.

 

그러나 이번에는 시간복잡도를 크게 줄이지 못했다.

파이썬3 기준 1등이 244ms이던데, 48ms를 어디서 줄여야할지 조금은 막막하다.

 

만약 개선점을 찾아내면 다시 포스팅을 할 예정이다.