호텔 대실(프로그래머스) 문제풀이

문제 

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

프로그래머스

 

문제 접근 방식

처음 문제를 봤을 때는 그리디 문제로 판단해서, 대실 종료 시각을 기준으로 오름 차순 정렬 후, 가장 많이 겹치는 방의 수를 구하는 방식으로 문제를 풀려고 했는데 잘 되지 않아서 풀이 방향을 바꿨다.

0:00~23:59 을 분 단위로 변환후 이에 대응하는 일차원 배열을 생성하고, book_time 의 예약 시간에 해당하는 시간에 1을 더해서 해당 시간에 사용 중인 객실을 표시한다. 이때, 예전 [파괴되지 않은 건물] 에서 특정 범위에 일괄적으로 수를 더하는 방법을 배웠기 때문에 해당 방식을 활용해서 문제를 풀었다.

 

 

 

 

시간 복잡도

모든 예약에 대해 시간을 변환 후 배열에 저장해야하기 때문에 O(N)이 걸리며, 시간 배열을 순회하며 누적 합을 구해서 최댓값을 구할 때 O(M)이 걸린다. 전체 시간복잡도는 O(N+M)이며, N과 M의 최댓값이 각각 1000, 1450(60*24+10) 이므로 시간 내에 동작한다.

 

코드

MAX=60*24
def solution(book_time):
	# 분 단위 배열
    total=[0]*(MAX+11)
    for start,end in book_time:
    	# 분 단위로 시간 변환
        s_hour,s_minute=map(int,start.split(":"))
        e_hour,e_minute=map(int,end.split(":"))
        s_time=s_hour*60+s_minute
        e_time=e_hour*60+e_minute+9
        
        # [시작 지점]에는 +1, [마지막 지점+1]에는 -1을 저장해서 이후 누적합을 구함
        total[s_time]+=1
        total[e_time+1]-=1
        
    for i in range(len(total)-1):
        total[i+1]+=total[i]
        
    return max(total)

 

 

회고

[파괴되지 않은 건물] 에서 특정 구간에 일괄적으로 수를 더하는 방식을 공부했던게 도움이 되었다.

https://break-a-leg.tistory.com/101

파괴되지 않은 건물(카카오) 문제풀이