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

 

 

1. 문제 설명

 

주어진 book_time 배열을 이용해, 호텔 방을 예약하는 문제입니다. 각 예약은 시작 시간과 종료 시간이 포함되어 있습니다. 이 문제는 예약을 처리하면서 동시에 필요한 최소 방의 개수를 구하는 문제입니다.

 

예약 시간은 [시작 시간, 종료 시간] 형태로 주어집니다. 각 예약은 겹치지 않게 처리되어야 하며, 방이 부족할 경우 새로 방을 할당해야 합니다. 한 예약이 종료된 후 최소 10분 이상 지나야만 다른 예약이 들어올 수 있습니다.

 

예약 시간이 주어졌을 때, 이 예약들을 처리하기 위한 최소 방의 수를 구하는 문제입니다.

 

프로그래머스

 

---

2. 해결 과정

이 문제는 방을 할당하고, 방을 관리하는 방식에 대해 고민해야 합니다. 예약이 들어올 때마다 기존 방에서 끝난 시간이 10분 이상 지난 방을 확인하고, 새로운 방을 할당할 수 있어야 합니다.

 

핵심 아이디어:

1. 예약 시간 순으로 정렬: 예약 시간은 시작 시간 기준으로 오름차순 정렬합니다.
2. 방 관리: 각 방에서 마지막 예약의 종료 시간을 추적하여, 새로 예약이 들어올 때 해당 방에서 10분 이상 시간이 경과했으면 그 방을 재활용할 수 있습니다.
3. 최대 방 개수 추적: 방을 할당할 때마다, 최대로 사용된 방의 개수를 추적하여 답을 도출합니다.

세부 구현:

• 예약이 들어올 때마다 방을 할당하거나 기존 방을 재활용할지 판단합니다.
• 종료 시간이 빠른 순으로 정렬하여, 10분 이상 지나면 방을 비우고 새로 예약을 할 수 있도록 합니다.

---

3. 구현 과정

1. 예약 시작 시간 기준으로 정렬: book_time 배열을 시작 시간을 기준으로 오름차순으로 정렬합니다. 이렇게 해야 먼저 들어오는 예약부터 처리할 수 있습니다.
2. 방 관리: 각 예약에 대해 방을 할당하는데, 방에 이미 있는 예약들의 종료 시간을 확인하여, 종료 시간이 10분 이상 지난 방을 비워두고 새 예약을 할 수 있도록 합니다.
3. 최대 방 개수 추적: rooms 배열에 예약이 끝난 시간 순으로 방을 할당합니다. 각 예약마다 방을 추가하고, 최대 방 개수를 추적하여 최종적으로 반환합니다.
4. 모든 예약을 처리 후 최종 방 개수 반환: 예약들을 모두 처리한 후, maxRoom 값을 반환하여 필요한 최소 방의 개수를 제공합니다.

    // 코드 작성 중 적어놓은 구현 주석 : 
    // 대실 시작 시각을 기준으로 솔팅 
    // 나갈 방 없으면 새로운 방에 추가 
    // 추가 후 솔팅 (대실 종료 시각 기준)
    // 나갈 방 있는지 확인 [0] (대실 종료 시각 < 대실 시작 시각) 
    // 들어올 때마다 Max 값 업데이트

 

4. 코드 구현

function solution(book_time) {
    let rooms = [];
    let maxRoom = 0; 

    function makeRoom(book) {
        rooms.push(book); 
        rooms.sort((a, b) => {
            const [aTime, aMin] = a[1].split(":"); 
            const [bTime, bMin] = b[1].split(":"); 
        
            const aTotalMinutes = parseInt(aTime) * 60 + parseInt(aMin);
            const bTotalMinutes = parseInt(bTime) * 60 + parseInt(bMin);
        
            return aTotalMinutes - bTotalMinutes; 
        }); 
        
        maxRoom = Math.max(maxRoom, rooms.length); 
    }

    book_time.sort((a, b) => {
        const [aTime, aMin] = a[0].split(":"); 
        const [bTime, bMin] = b[0].split(":"); 
        
        const aTotalMinutes = parseInt(aTime) * 60 + parseInt(aMin);
        const bTotalMinutes = parseInt(bTime) * 60 + parseInt(bMin);
        
        return aTotalMinutes - bTotalMinutes;
    });

    book_time.forEach((book) => {
        if (rooms.length === 0) return makeRoom(book);
        
        const [sTime, sMin] = book[0].split(":"); 
        const [eTime, eMin] = rooms[0][1].split(":"); 
        
        const sTotalMinutes = parseInt(sTime) * 60 + parseInt(sMin);
        const eTotalMinutes = parseInt(eTime) * 60 + parseInt(eMin);
        
        let gap = sTotalMinutes - eTotalMinutes; 
        if (gap >= 10) {
            rooms.splice(0, 1); 
        }
        makeRoom(book);
    });

    return maxRoom;
}

 

---

5. 결론

이 문제는 예약 시간 관리와 방 배정을 효율적으로 처리하는 문제였습니다. 그리디 알고리즘을 사용하여 방을 최소화하고, 종료 시간에 10분 이상의 간격을 두고 예약을 배치하는 방식으로 해결했습니다.

 

모든 예약을 처리한 후 방의 수를 추적하여 최소 방 개수를 구하는 이 알고리즘은 O(n log n) 의 시간 복잡도를 가집니다.

예약을 시간 순으로 정렬하고 각 예약마다 방을 할당하는 과정에서 로그 복잡도가 발생합니다.