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

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

프로그래머스

 

고찰 과정

처음에는 호텔 입실 시간을 기준으로 오름차순 정렬을 한 후 적절한 기준을 세워서 적절한 호텔 객실 수를 구하면 될 것 같다는 생각을 하였습니다. 하지만 어떤 기준을 세워서 호텔 객실 수를 구하면 좋을지 그 과정에서 고민하는 일에 시간이 좀 걸렸습니다.

 

문제를 분석한 결과 이 문제는 그리디 문제로 입실 시간과 퇴실 시간을 하나로 묶을 필요가 없이 그냥 시간순으로 정렬하여(시간이 같다면 퇴실 시간을 우선하도록 정렬) 적절한 호텔 객수를 구하면 되는 문제였습니다. 해당 호텔 시간이 입실인지 퇴실인지만 구분만 된다면 입실 시간에 대해서는 +1, 퇴실 시간에 대해서는 -1을 표시를 하여 그에 따른 적절한 호텔 객실수를 구할 수가 있었습니다. 이해를 돕기 위해서 아래 그림의 예시를 바탕으로 설명하겠습니다.

 

위 그림에서 두 개의 대실 시간이 있다고 가정해봅시다. 여기서 왼쪽 인자는 시간대를 기준으로 오름차순 정렬했을 때의 번호를 취급한 값이고, 두 번째 인자는 해당 시간이 입실인지, 퇴실인지 구분하기 위한 값입니다. 이 구분값을 활용하여 적절한 호텔 객실 수를 구할 것입니다. 호텔 객실의 수를 산정하자면 다음과 같은 과정으로 구할 수가 있습니다.

현재 카운팅을 위한 변수, 최적의 객실 수를 위한 변수가 존재한다고 할 때 다음과 같은 방식으로 계산을 할 수가 있습니다.

처음에는 최적의 객실 수는 0인 상황입니다.

 

1. 1번 시간대의 오른쪽 인자를 통해서 카운팅을 진행해준다.

    -> 현재 카운팅: 1

    -> 최적의 객실 수: max(최적의 객실 수, 현재 카운팅)  = 1

2. 2번 퇴실 시간을 만났으므로 -1의 연산에 의해서 현재 카운팅은 0이 됩니다. 그리고 최적의 객실 수는 여전히 1이 됩니다.

    -> 현재 카운팅: 0

    -> 최적의 객실 수: max(최적의 객실 수, 현재 카운팅)  = 1

3. 마찬가지로 두 번째 대실 시간도 1과 2의 과정을 반복하여 최적의 객실 수를 갱신할 수 있습니다.  결국 최적의 객실 수는 1이 됩니다.

 

여기서 주의할 점은 시간대가 같은 호텔 시간의 경우에는 퇴실 시간인 유형의 시간을 우선 배치하여 정렬을 해야 배정할 수 있는 최소 호텔 객실 수를 도출할 수 있다는 점입니다. 참고로 청소 시간을 따로 적용을 하지 않았는데 위 그림에서는 퇴실 시간을 적용을 안해도 퇴실 시간이 다음 입실 시간을 넘어가버리는 경우가 없기에 그대로 진행했습니다. 실제로 문제를 풀 때는 각 퇴실 시간에 10분을 전부 더해준 다음 문제를 해결해야 합니다.

 

이를 코드로 구현하면 됩니다. 참고로 시간은 분으로 변경한 후 해결하였습니다.

한 시간대를 무조건 묶어서 생각해야한다는 고정관념을 깨뜨리게 해준 문재였습니다. 

---

코드

import java.util.*;

class Solution {
    
    private static final int START = 1;
    private static final int END = -1;
    
    public int solution(String[][] book_time) {
        List<int[]> times = new ArrayList<>();
        
        for (String[] book : book_time) {
            int start = takeMinutes(book[0]);
            int end = takeMinutes(book[1]) + 10;
            times.add(new int[]{start, START});
            times.add(new int[]{end, END});
        }
        
        Collections.sort(times, (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
        
        int answer = 0;
        int currentRooms = 0;
        
        for (int[] time : times) {
            currentRooms += time[1];
            answer = Math.max(answer, currentRooms);
        }
        
        return answer;
    }
    
    private int takeMinutes(String time) {
        String[] timeInfo = time.split(":");
        return Integer.parseInt(timeInfo[0]) * 60 + Integer.parseInt(timeInfo[1]);
    }
}