[알고리즘] 호텔대실 프로그래머스 Lv.2 파이썬

코드: Algorithm_test/Python3/프로그래머스/2/155651. 호텔 대실 at main · ddalkyTokky/Algorithm_test · GitHub

1. 큐를 활용하자

가장 먼저 들었던 생각은 큐를 활용해서, 최대 큐의 크기를 정답으로 내놓으면 된다였다. 예를들어, 예약 시간이 a, b, c, d, e 순으로 있다고 해보자. (시작 시간 기준)

수행 순서	큐 상태
a 가 큐에 들어간다.	[a]
b 들어가기 전, b 의 시작 시간 기준으로 큐 안에 있는 녀석들중 대실 시간이 끝난 녀석이 있는지 확인한다. (정리하는 시간까지 +10분)	a의 시간이 아직 안 끝났다면, [a] a의 시간이 끝났다면, []
b 를 넣는다.	a의 시간이 아직 안 끝났다면, [a, b] a의 시간이 끝났다면, [b]
c 도 마찬가지로 넣기전에 큐를 순회하면서 시간이 종료된 녀석을을 삭제한다.	...

아주 간단하죠?

2. 정렬

근데, 입력값 book_time 이 정렬이 안되있길래 시작시간 기준으로 정렬을 추가해줬다.

3. 최종 코드

allow 함수는 2번째 인자의 시간 기준으로, 1번째 인자의 시간이 앞인지 뒤인지를 판단한다. 간단하게, 방 빼야 하는 시간이 도래했는지 아닌지를 판단한다.

def allow(str1, str2):
    h1 = int(str1[0 : 2])
    m1 = int(str1[3 : ])
    h2 = int(str2[0 : 2])
    m2 = int(str2[3 : ])
    
    m1 += 10
    if(m1 >= 60):
        h1 += 1
        m1 -= 60
        
    if(h2 > h1):
        return True
    elif(h1 == h2):
        if(m2 >= m1):
            return True
    return False

def solution(book_time):
    queue = []
    max_queue_size = 1
    
    book_time.sort()
    
    for time in book_time:
        for q in queue:
            if(allow(q[1], time[0])):
                queue.remove(q)
                break
        queue.append(time)
        if(max_queue_size < len(queue)):
            max_queue_size = len(queue)
    
    return max_queue_size

4. 시간 복잡도

행위	시간 복잡도
정렬	O(N logN)
순회 (최선) - 큐가 완전히 비기만 할때	O(N)
순회 (최악) - 큐가 항상 가득 찰때	O(N^2)
최종	O(N^2) ~ O(N logN)