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

문제 설명 

1. 사용한 객실은 10분 청소후 다음 손님이 사용할 수 있다. 

2. book_time 배열에 각 예약별 대실 시작 시각과 대실 종료 시간이 주어진다. 

3. 이때 사용하는 최소 객실 수를 구하는 문제이다. 

 

 

풀이 

모든 시간을 분으로 변경해주고 시간 순으로 정렬을 했다. 

time 배열에 시간 순으로 오는 손님들의 (대실 종료 시간 + 10)을 저장했다. 

새로운 예약 손님의 대실 시작 시간이 time 배열의 최소값보다 크다면 해당 객실은 사용 가능하므로 새로운 예약의 대실 종료 시간으로 대체했다.

새로운 예약 손님의 대실 시작 시간이 time 배열의 최소값보다 작다면 새로운 객실을 주어야 하므로 time에 대실 종료 시간을 넣어주었다. 

 

코드

def solution(book_time):
    
    # 모든 시간을 분으로 표시
    book_min=[]
    for s,e in book_time:
        srt_min=int(s[:2])*60+int(s[3:])
        end_min=int(e[:2])*60+int(e[3:])
        book_min.append([srt_min,end_min])
        
    book_min.sort()
    
    time=[] # 대실 종료 시간 저장 
    for srt,end in book_min:
        if len(time)==0:
            time.append(end+10)
            continue
        
        fast_end=min(time)
        if fast_end<=srt:
            time[time.index(fast_end)]=end+10
        else:
            time.append(end+10)
        
    
    return len(time)

 

 

다른 풀이

00:00~23:59에 대한 배열을 만들어서 각 예약의 "분"에 해당하는 시간에 모두 +1을 해주고 해당 배열의 최댓값을 반환한 풀이도 있다. 

이 풀이에서는 동시간대에 겹치는 예약의 수를 찾고 그중 최댓값을 찾아 필요한 최소 객실을 수를 찾아주었다.  

 

누적합으로 구할 수도 있다.  https://break-a-leg.tistory.com/123