KATA#100

WHAT IS KATA?

KATA는 기술과 기술 향상에 초점을 맞춘 코드 챌린지입니다.
일부는 프로그래밍 기본 사항을 교육하는 반면 다른 일부는 복잡한 문제 해결에 중점을 둡니다.

이 용어는 The Pragmatic Programmer 라는 책의 공동 저자인 Dave Thomas 가
무술에서 일본의 카타 개념을 인정하면서 처음 만들어졌습니다.
Dave의 개념 버전은 코드 카타를 프로그래머가
연습과 반복을 통해 기술을 연마하는 데 도움이 되는 프로그래밍 연습으로 정의합니다.

드디어 100번 째 KATA 달성 : )

---

- PYTHON

---

✔️ 문제 #1: 호텔 대실

✔️ 제출 코드

✔️ 코드 분석

from heapq import *

def solution(book_time):
    # HH:MM 형식의 시간을 분(minute)으로 변환하는 함수 생성
    def time_to_minutes(time):
        hours, minutes = map(int, time.split(":"))
        return hours * 60 + minutes

    # 예약 시간을 시작 시간과 종료 시간(청소 시간 포함)으로 변환하여 bookings 리스트에 저장
    bookings = []
    for start, end in book_time:
        start_time = time_to_minutes(start)
        end_time = time_to_minutes(end) + 10  # 청소 시간 10분 추가
        bookings.append((start_time, end_time))

    # 예약을 시작 시간 기준으로 정렬
    bookings.sort()

    # 객실의 종료 시간을 관리하는 최소 힙 (우선 순위 큐)
    rooms = []

    for start, end in bookings:
        # 현재 시작 시간 전에 종료되는 객실이 있으면 해당 객실 재사용
        if rooms and rooms[0] <= start:
            heappop(rooms)  # 종료된 객실 제거

        # 현재 예약의 종료 시간을 힙에 추가하여 새로운 객실 또는 재사용된 객실의 종료 시간 갱신
        heappush(rooms, end)

    # 필요한 객실의 수는 힙에 남아있는 종료 시간의 수와 동일
    return len(rooms)
    

---

✔️ CHECK POINT

• PYTHON

• 시간 변환 함수

  • "HH" 형식의 시간을 분 단위로 변환하는 time_to_minutes(time) 함수 생성

def time_to_minutes(time):
    hours, minutes = map(int, time.split(":"))
    return hours * 60 + minutes

• 예약 시간 변환 및 정렬
  • 주어진 예약 시간을 시작 시간과 종료 시간(청소시간 10분 포함)으로 변환한 후,
    bookings 리스트에 저장
  • 예약을 시작 시간 기준으로 정렬

bookings = []
for start, end in book_time:
    start_time = time_to_minutes(start)
    end_time = time_to_minutes(end) + 10
    bookings.append((start_time, end_time))
bookings.sort()

• 힙을 이용한 객실 관리
  • 객실의 종료 시간을 관리하는 최소 힙 rooms 를 사용
  • 각 예약의 시작 시간과 종료 시간을 순회하면서,
    현재 시작 시간 전에 종료되는 객실이 있으면 해당 객실을 재사용하고,
    그렇지 않으면 새로운 객실이 필요
  • 현재 예약의 종료 시간을 힙에 추가하여,
    새로운 객실 또는 재사용된 객실의 종료 시간을 갱신

rooms = []

for start, end in bookings:
	# 힙이 비어 있지 않고(rooms), 
    # 힙의 최솟값(rooms[0], 즉 가장 빨리 끝나는 객실의 종료 시간)이 
    # 현재 예약의 시작 시간(start)보다 작거나 같으면, 객실 재사용
	# heappop(rooms)를 통해 가장 빨리 끝나는 객실의 종료 시간을 힙에서 제거, 
    # 해당 객실이 새로운 예약에 재사용된 것을 의미
    if rooms and rooms[0] <= start:
        heappop(rooms)
    heappush(rooms, end)

• 최소 힙(우선순위 큐) : 최소 힙을 사용하여 항상 가장 빨리 끝나는 객실의 종료 시간을 쉽게 접근할 수 있다.
• 객실 재사용 : 현재 예약의 시작 시간 전에 종료되는 객실이 있다면 해당 객실을 재사용한다.
• 종료 시간 갱신 : 현재 예약의 종료 시간을 힙에 추가하여, 새로운 객실 또는 재사용된 객실의 종료 시간을 갱신한다.

• 결과 반환
  • 필요한 객실의 수는 힙에 남아있는 종료 시간의 수와 동일

return len(rooms)

---