[알고리즘] 프로그래머스 Lv2 호텔 대실

문제

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

풀이 과정

문제는 매우 간단하다.
주어진 대실 예약 리스트를 만족시키는 최소한의 방의 개수를 구하는 것

숙박이 아니라 대실이라서 시간이 한정적이다.
따라서, 각 분을 인덱스로 가지는 리스트를 만들어서 풀 수도 있을 것이다.

나는 rooms라는 리스트를 만들어서 시간을 요소로 추가하고 들어오는 대실 시간을 비교해서 넣고 빼고 하는 방식으로 코드를 작성했다.

코드

def solution(book_time):
    for i, time in enumerate(book_time):
        book_time[i] = [int(time[0][0:2]) * 60 + int(time[0][3:]), int(time[1][0:2]) * 60 + int(time[1][3:]) + 10] 
        # 시간을 분으로 바꾸는 코드인데, 이 부분을 따로 함수로 만든 사람이 많았다.
    book_time.sort(key=lambda x: (x[0], x[1]))
    # print(book_time)

    rooms = [book_time[0]]
    for time in book_time[1:]:
        start = time[0]
        for n_room, room in enumerate(rooms):
            if room[1] <= start: # 방에 이미 있는 손님의 퇴실 시간 + 10분 <= 들어올 손님의 입실 시간 이면, 그 방에 손님 넣고 break
                rooms[n_room] = time
                break

        else:
            rooms.append(time)

    answer = len(rooms)
    return answer

다른 사람의 풀이

Counter 내장함수 사용

from collections import Counter
def solution(book_time):
    def get_time(t):
        HH, MM = map(int, t.split(":"))
        return HH*60 + MM
    m = 0
    n = 0

    in_time = Counter([get_time(b[0]) for b in book_time])
    out_time = Counter([get_time(b[1])+10 for b in book_time])
    total_time = set(list(in_time.keys())+list(out_time.keys()))
    total_time = list(total_time)
    total_time.sort()
    for t in total_time:
        n -= out_time[t]
        n += in_time[t]
        m = max(m, n)
    return m

Counter를 이용해서 book_time에 있는 시간과 횟수를 세고 total_time을 정렬한 다음, 입실이면 +횟수, 퇴실이면 -횟수하는 방식과 각 반복문에서의 n의 최댓값을 구하는 방식

각 분을 인덱스로 가지는 리스트 사용

def solution(book_time):
    time_table = [0 for _ in range(60 * 24)] # 0시 00분 ~ 23시 59분의 각 분을 인덱스로 가지는 리스트 생성
    for start, end in book_time:
        start_minutes = 60 * int(start[:2]) + int(start[3:])
        end_minutes = 60 * int(end[:2]) + int(end[3:]) + 10

        if end_minutes > 60 * 24 - 1: # 인덱스가 time_table을 넘지 않도록 방어코드 작성
            end_minutes = 60 * 24 - 1

        for i in range(start_minutes, end_minutes):
            time_table[i] += 1
            
    return max(time_table) # 시간이 겹친다 -> 방이 겹치는 시간 횟수만큼 필요하다
    # 추가 아이디어: 위의 반복문 대신에 시작 시간은 +1, 끝 시간은 -1만 하고 마지막에 max(누적합)을 구해도 됨

0시 00분 ~ 23시 59분의 각 분을 인덱스로 가지는 리스트를 생성해서 book_time에서 입실~퇴실 사이의 분에 대해 모두 +1하는 식으로 book_time을 순회한 후, max값을 구하는 방식

시간은 더 오래 걸릴 것 같지만, 현재 나의 수준에서는 아래 방식이 더 직관적으로 와닿고 다음에 써먹을 수 있을 것 같다.