프로그래머스 | Level 2 | 호텔 대실

Programmers | Level 2 | 호텔 대실

Problems

• 📘 Src: Programmers
• 🗂️ Cat: Simulation

󰧭 Description

호텔을 운영 중인 코니는 최소한의 객실만을 사용하여 예약 손님들을 받으려고 합니다. 한 번 사용한 객실은 퇴실 시간을 기준으로 10분간 청소를 하고 다음 손님들이 사용할 수 있습니다.

예약 시각이 문자열 형태로 담긴 2차원 배열 book_time이 매개변수로 주어질 때, 코니에게 필요한 최소 객실의 수를 return 하는 solution 함수를 완성해주세요.

 Constraints

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

󰦕 Examples

book_time	result
[["15:00", "17:00"], ["16:40", "18:20"], ["14:20", "15:20"], ["14:10", "19:20"], ["18:20", "21:20"]]	3
[["09:10", "10:10"], ["10:20", "12:20"]]	1
[["10:20", "12:30"], ["10:20", "12:30"], ["10:20", "12:30"]]	3

Solutions

󰘦 Code

import java.util.*;

class Solution {
    public int solution(String[][] book_time) {
        int[] slots = new int[1440];  // 하루를 분 단위로 나눈 배열
        int rooms = 0;  // 필요한 최소 객실 수

        for (String[] time : book_time) {
            // 시작 시간과 종료 시간을 분으로 변환
            int start = timeInMinutes(time[0]);
            int end = Math.min(timeInMinutes(time[1]) + 10, 1440);  // 청소 시간 포함, 최대 1440(23:59)분까지만 포함

            // 해당 시간대의 객실 사용 여부 업데이트
            for (int i = start; i < end; i++) {
                slots[i]++;  // 해당 시간대에 객실 사용 증가
                rooms = Math.max(slots[i], rooms);  // 필요한 객실 수 업데이트
            }
        }

        return rooms;  // 최종 필요한 최소 객실 수 반환
    }

    // "HH:MM" 형식을 분 단위로 변환
    private int timeInMinutes(String bookTime) {
        String[] time = bookTime.split(":");
        return Integer.parseInt(time[0]) * 60 + Integer.parseInt(time[1]);
    }
}

 Approach

이 문제는 예약된 객실을 효율적으로 배치하여 필요한 최소 객실 수를 구하는 시뮬레이션 문제입니다. 예약 시간의 시작과 종료 시점을 분 단위로 변환해 하루 동안 객실 수요를 추적하고, 최대 겹치는 시간을 계산하여 해결할 수 있습니다.

1. 문제 분석

호텔 예약 시간대를 기준으로 객실의 사용 시간을 추적하여, 최소한의 객실 수를 계산하는 문제입니다. 각 예약은 일정 시간 동안 객실을 사용하고, 퇴실 후에는 10분의 청소 시간이 추가됩니다. 중요한 점은 예약 시간이 겹칠 때 발생하는 추가 객실 필요량을 효율적으로 관리하여 최소한의 객실 수를 계산하는 것입니다.

예약 시간은 24시간 형식으로 주어지며, 이를 처리하기 위해 하루를 1,440분(24시간 × 60분)으로 변환해 시간대를 관리할 수 있습니다. 각 예약의 시작 시간부터 종료 시간(청소 시간 포함)까지 겹치는 시간대를 추적하며, 그 중 최대값을 구하는 방식으로 최소 객실 수를 계산해야 합니다.

중요한 고려 사항으로는 예약이 끝난 후 10분의 청소 시간이 포함된다는 점과, 이로 인해 다음 예약과의 간격이 최소 10분이어야 한다는 점이 있습니다.

2. 접근 방식

이 문제를 해결하기 위해 하루를 분 단위로 나누어 각 시간 슬롯에서 몇 개의 객실이 사용 중인지 추적합니다. 이를 위해 다음과 같은 접근 방식을 사용합니다:

• 분 단위 변환: 주어진 예약 시간을 "HH:MM" 형식에서 분 단위로 변환하여 계산합니다.
• 슬롯 배열 활용: 하루 1,440분을 배열로 나누어 각 시간 슬롯에서 객실이 사용 중인지 여부를 기록합니다.
• 최대 겹치는 시간대 추적: 예약 시간이 겹치는 시간대에서 객실 수를 계산하여 최소한의 객실 수를 구합니다.

3. 초기화 및 분 단위 변환

먼저, 하루를 1,440분으로 나누어 각 시간대의 객실 사용 여부를 기록할 배열을 초기화합니다. 예약 시간이 "HH:MM" 형식으로 주어지므로, 이를 분 단위로 변환하여 계산합니다. 또한, 필요한 최소 객실 수를 추적할 변수를 초기화합니다.

int[] slots = new int[1440]; // 하루를 1,440분으로 나눈 배열
int rooms = 0;  // 필요한 최소 객실 수

4. 시각을 분 단위로 변환

예약 시간은 "HH:MM" 형식으로 주어지므로 주어진 배열 book_time을 순회하는 과정에서 이를 처리하기 위해 먼저 분 단위로 변환합니다. 이렇게 분 단위로 변환하여 slots 배열에 방의 사용 시간을 기록하면서, 객실의 사용 여부를 세밀하게 추적할 수 있습니다. 각 예약의 종료 시각에는 청소 시간을 고려하여 10분을 추가하며, 하루는 1,440분으로 제한되기 때문에 자정을 넘어가는 시간을 방지하기 위해 최대 값을 1,440으로 설정합니다. 이를 통해 각 예약의 실제 사용 시간대를 정확하게 관리할 수 있습니다.

for (String[] time : book_time) {
    int start = timeInMinutes(time[0]);  // 시작 시간
    int end = Math.min(timeInMinutes(time[1]) + 10, 1440);  // 종료 시간 + 청소 시간
    ...
}

// "HH:MM" 형식을 분 단위로 변환
private int timeInMinutes(String bookTime) {
    String[] time = bookTime.split(":");
    return Integer.parseInt(time[0]) * 60 + Integer.parseInt(time[1]);
}

5. 각 예약 시간대에 대한 처리

더 많은 객실이 필요한 경우는 동시간대에 예약이 겹치는 상황입니다. 각 예약의 시작 시간부터 종료 시간까지 해당 시간대의 슬롯 값을 1씩 증가시켜 겹치는 시간대의 방 사용을 기록합니다. 이때, 슬롯 값 중 최대값을 추적하면 최종적으로 필요한 방의 개수를 계산할 수 있습니다.

for (String[] time : book_time) {
    ...
    
    // 각 예약의 시작 시간부터 종료 시간(+청소 시간)까지 처리
    for (int i = start; i < end; i++) {
        slots[i]++;  // 해당 시간대에 객실 사용 중임을 기록
        rooms = Math.max(slots[i], rooms);  // 최대 객실 수 갱신
    }
}

6. 최종 결과 반환

모든 예약 시간대를 처리한 후, 최대 겹친 객실 수가 필요한 최소 객실 수이므로, 이를 반환합니다.

// 최종 필요한 최소 객실 수 반환
return rooms;

󰄉 Complexity

• ⏳ TC: O(n)
• 💾 SC: O(1)

예약 시간은 최대 1,000개까지 주어질 수 있으며, 각 예약 시간을 처리하는 데 걸리는 시간은 예약당 고정된 분 단위 배열을 사용하여 O(n)입니다. 공간 복잡도는 하루를 1,440분으로 나눈 배열을 사용하므로 O(1)로 고정됩니다.