프로그래머스 호텔대실 파이썬

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

프로그래머스

내 풀이

---

import heapq

def getTime(timeStr):
    time = timeStr.split(":")
    return int(time[0]) * 60 + int(time[1])


def solution(book_time):
    answer = 0
    booklist = []
    n = len(book_time)
    if n == 1:
        return 1
    for book in book_time:
        startTime = getTime(book[0])
        endTime = getTime(book[1]) + 10
        heapq.heappush(booklist, (startTime, endTime))
    
    while booklist:
        answer+= 1
        curStart, curEnd = heapq.heappop(booklist)
        q = []
        while booklist:
            start, end = heapq.heappop(booklist)
            if curEnd > start:
                q.append((start, end))
            else:
                curEnd = end
        heapq.heapify(q)
        booklist = q
    return answer

---

풀이 설명

1. 주어진 예약 시간을 시작시간으로 정렬 - heap 사용

2. heap을 순회

    2.1 같은 room에 있는 것들을 pop

    2.2 같은 room에 있지 않으면 따로 저장

3. 2.2에서 따로 저장한 것들을 heapify 하여 정렬 후 heap이 없을 때까지 1번 단계로 다시 반복

---

EX)

book_time: [["15:00", "17:00"], ["16:40", "18:20"], ["14:20", "15:20"], ["14:10", "19:20"], ["18:20", "21:20"]]

 

 

초기값: [["14:10", "19:20"] ,["14:20", "15:20"], ["15:00", "17:00"], ["16:40", "18:20"],  ["18:20", "21:20"]]

첫 번째 1~3번 진행 후 : [["14:20", "15:20"], ["15:00", "17:00"], ["16:40", "18:20"],  ["18:20", "21:20"]]

두 번째 1~3번 진행 후: [["16:40", "18:20"],  ["18:20", "21:20"]]

---

다른 풀이:

누적합

def solution(book_time):
    check = [0]*1440    # 0 ~ 23:59 까지를 분으로 체크하기 위한 list 생성

    for times in book_time:
        # 입력값을 분으로 변환
        sh, sm = map(int, times[0].split(':'))
        eh, em = map(int, times[1].split(':'))
        start = sh * 60 + sm
        end = eh * 60 + em + 10    # 청소시간 10분 포함

        if end > 1440:    # 24시를 넘어가는 경우 24시로 통일
            end = 1440

        for idx in range(start, end):    # 대실하는 시간에 체크
            check[idx] += 1

    return max(check)    # 방의 수가 가장 많이 대실하고 있을 때 값을 출력