호텔 대실

프로그래머스

 

풀이 1

def test(arr):
    new_arr = []
    
    for i in range(2):
        time = arr[i]
        hour, minute = time.split(":")
        new_time = int(hour) * 60 + int(minute)
        
        # 대실 종료시각의 경우 청소시간을 포함해서 10분을 추가
        if i == 1:
            new_time += 10
        
        # 대실 종료시각이 23:50 이상이라면, 청소시간을 포함해서 23:59로 바꿔버림
        if i == 1 and new_time >= 1350:
            new_time = 1359
        
        new_arr.append(new_time)
        
    return new_arr


def solution(book_time):
    answer = 0
    
    # 대실 시작시간, 대실 종료시간을 분으로 저장
    # 대실 종료시간에는 청소시간 10분을 추가해서 저장
    book_minute = list(map(test, book_time))
    
    book_minute.sort(key=lambda x: x[0]) # 대실시작시간 기준으로 정렬
    n = len(book_minute)
    
    for i in range(n):
        current = book_minute[i] # 현재 확인할 손님
        temp = 1 # 현재 확인할 손님이 입실했을 때, 필요한 방의 수(최소 1개)
        # 0 ~ i-1번째 손님이 현재 방에 있는지 확인
        for j in range(i):
            # 만약 현재 입실할 손님의 입실 시간이 지금 입실 중인 손님의 퇴실 시간 이전이라면
            if current[0] < book_minute[j][1]:
                temp += 1 # 방을 1개 더 추가
        
        # 방의 최댓값을 갱신
        answer = max(temp, answer)
        
        
    return answer

 

내가 생각해낸 풀이

이 풀이는 이중반복문을 돈다.

그래서 답은 맞추지만 시간 복잡도가 별로임

 

---

풀이 2

def test(arr):
    new_arr = []
    
    for i in range(2):
        time = arr[i]
        hour, minute = time.split(":")
        new_time = int(hour) * 60 + int(minute)
        
        # 대실 종료시각의 경우 청소시간을 포함해서 10분을 추가
        if i == 1:
            new_time += 10
        
        # 대실 종료시각이 23:50 이상이라면, 청소시간을 포함해서 23:59로 바꿔버림
        if i == 1 and new_time >= 1350:
            new_time = 1359
        
        new_arr.append(new_time)
        
    return new_arr


def solution(book_time):
    answer = 0
    
    # 대실 시작시간, 대실 종료시간을 분으로 저장
    # 대실 종료시간에는 청소시간 10분을 추가해서 저장
    book_minute = list(map(test, book_time))
    
    # 시작, 종료 대실 시간에 따른 방 수를 저장하는 리스트
    check_time = [0 for _ in range(60 * 24 + 10)]
    
    # 대실 시작시간의 경우 + 1, 대실 종료시간의 경우 - 1
    for start, end in book_minute:
        check_time[start] += 1
        check_time[end] -= 1
        
    # 현재 필요한 방 개수
    room_cnt = 0
    
    # 00:00 ~ 23:59까지 반복문을 돈다.
    # 반복문을 돌면서 입실하는 경우 + 1, 퇴실하는 경우 -1을 통해 해당 시간에 필요한 방 수를 저장, 갱신
    for i in range(len(check_time)):
        room_cnt += check_time[i]
        check_time[i] = room_cnt
    
    # check_time의 최댓값이 필요한 최소 객실 수
    answer = max(check_time)
    
    return answer

 

구글링을 통해 시간복잡도를 개선한 풀이

반복문을 한 번만 돌고도 풀 수 있다.

 

핵심 로직은 각 입실시간, 퇴실 시간에서 입실 시간은 +1, 퇴실 시간은 -1을 해줌으로써 특정 시간의 방 수를 갱신, 저장한다는 것이다.