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

링크

문제 설명

입력으로 [입실 시간, 퇴실 시간] 쌍으로 이루어진 리스트가 주어진다. 예약 시간동안 그 방은 다른 사람이 사용할 수 없으며 청소시간이 있기 때문에 퇴실시간이 지난 후 10분 뒤에 새로운 손님을 받을 수 있다. 예약 목록이 주어졌을 때 필요한 최소 객실의 수를 구하는 문제이다.

제한사항

def solution(book_time: List) -> int:
    answer = 0
    return answer

• 1 ≤ book_time의 길이 ≤ 1,000
  • book_time[i]는 ["HH:MM", "HH:MM"]의 형태로 이루어진 배열입니다
    • [대실 시작 시각, 대실 종료 시각] 형태입니다.
  • 시각은 HH:MM 형태로 24시간 표기법을 따르며, "00:00" 부터 "23:59" 까지로 주어집니다.
    • 예약 시각이 자정을 넘어가는 경우는 없습니다.
    • 시작 시각은 항상 종료 시각보다 빠릅니다.

풀이

라인 스위핑으로 문제를 풀었다. 시작시간과 종료시간을 한 리스트에 넣고, 리스트를 순회하며 시작시간일 경우 +1, 종료시간일 경우 -1으로 계산해 최대값을 구한다.

제출 코드

def to_min(s):
    h, m = s.split(":")
    return int(h) * 60 + int(m)

def solution(book_time):
    arr = [] # (minute, 's' or 'e')
    for s, e in book_time:
        s = to_min(s)
        e = to_min(e) + 10
        arr.append((s, 's'))
        arr.append((e, 'e'))

    arr.sort()
    cnt = 0
    max_cnt = 0
    for val, flag in arr:
        if flag == 's':
            cnt += 1
        else:
            cnt -= 1
        max_cnt = max(cnt, max_cnt)

    return max_cnt