[프로그래머스] 호텔 대실 (Python)

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/155651#

프로그래머스

소스 코드

def solution(book_time):
    table =[]
    room = 0 # 방 개수

    for start,end in book_time:
        table.append([int(start[:2])*60 + int(start[3:]), 1]) # 시작
        table.append([int(end[:2])*60 + int(end[3:])+10, 0]) # 종료
    table.sort() # 시간순으로 정렬

    now = 0 # 현재 방 개수
    for time, state in table:
        if state == 1: # 시작 시간인 경우
            now += 1
        else: # 종료 시간인 경우
            now -= 1
        
        room = max(room, now)

    return room

해설

• 그리디

일종의 스택 개념으로 느껴지는 그리디 문제로 보입니다.

처음에는 종료 시간을 기준으로 스택처럼 풀이하려고 생각했었는데,

다른 분의 풀이를 보니 굳이 그럴 필요 없이 시작/종료 시간 여부로만 카운트가 가능했습니다.

 

위 풀이는 크게 두 파트로 나뉘어져 있습니다.

리스트의 요소들을 정수 형태로 변환하는 부분, 그리고 각 리스트의 원소를 꺼내어 살펴보는 부분입니다.

각 파트는 선형적으로 리스트를 탐색하는 것이므로 시간 복잡도는 book_time 리스트의 길이가 N이라고 했을 때,

O(N)이 될 것입니다.

(내장 함수를 이용한 정렬까지 포함하면 O(NlogN)입니다)

 

핵심은 아래의 방 개수를 세는 부분인데, 우리는 이미 시간순으로 리스트를 정렬했다는 점에 주목해야 합니다.

즉, 시간을 뜻하는 정수가 시작이든지 끝이든지 상관없이 정렬을 했기 때문에,

여기서 나온 숫자가 시작 시간이라면 방이 추가로 필요하고, 그렇지 않으면 방을 빼도 괜찮다는 뜻이 됩니다.

 

예를 들어 (900,1), (930,0), (1010,1) 과 같은 상황이라면,

9시에 입장(1개 추가), 9시 30분에 퇴장(1개 감소), 10시 10분에 입장(1개 추가)가 될 것입니다.

이때 각 이벤트마다 현재 활성화 되어있는 방의 개수를 현재까지의 최대 방 개수와 비교하여 갱신해주면 됩니다.