프로그래머스 - 호텔 대실(Java)

누적합 문제입니다.

 

일반적으로 배열에 공간이 비어있는지 확인하기 위해서 0과 0이 아닌 숫자를 사용합니다.

0은 비어있다는 뜻이고, 0이 아니면 공간이 차 있다는 뜻입니다.

[3, 7]까지 배열로 공간을 채워 보겠습니다.

여기서 추가로 [4, 8]까지의 공간을 채워 보겠습니다.

이렇게 연속된 공간을 채우는 방법은 일반적으로 두 번의 반복문을 사용합니다.

int[] arr = new int[11];

for(int i=3; i<=7; i++) arr[i] += 1;
for(int i=4; i<=8; i++) arr[i] += 1;

 

이런 반복문의 방법으로 배열을 채우는 경우가 많아지면 시간이 매우 오래 걸리게 됩니다.

 

이 연속된 공간을 채우는 방법을 단 한번의 반복문으로 끝낼 수 있게 하는 방법이 누적합 입니다.

우선 시작의 위치에 1을 추가하고 끝+1 위치에 -1을 추가합니다.

그런 다음, 뒤로 진행하면서 이전의 값을 더하면 됩니다.

 

[3,7] 과 [4,8]의 시작 위치는 각각 3과 4 입니다.

끝+1은 8과 9 입니다.

이를 표현하면 다음과 같습니다.

이제 누적합을 하면 됩니다. 

누적합은 현재 위치에서 이전 위치의 값을 더하면 됩니다.

int[] arr = new int[11];

arr[3] = 1;
arr[4] = 1;
arr[8] = -1;
arr[9] = -1;

for(int i=1; i<11; i++) arr[i] += arr[i-1];

 

 

시작과 끝 위치를 표시만 하면 단 한번의 반복문으로 배열을 채울 수 있다는 것을 알게 되었습니다.

 

다시 문제로 돌아가 볼까요?

문제에서 입실 시간과 퇴실 시간이 주어집니다.

문제에서 시간의 최소 단위는 분(minute)입니다.

즉, 시간을 분으로 계산하고 입실시간과 퇴실 시간을 배열에 기록하여 누적합을 하면

각 사람들이 겹치는 시간대를 알 수 있습니다.

사람들이 겹치면 새로운 방이 필요하기 때문에, 배열에 최대로 저장된 값이 최소로 필요한 방의 값이 됩니다.

 

단, 퇴실 이후 청소로 인해 10분간 방을 사용할 수 없다는 것을 까먹으시면 안됩니다.

청소 시간은 퇴실 시간에 더해주시면 됩니다.

 

[구현 코드]

class Solution {
    private static final int MAX_TIME = 1_450; // 24*60 + 10;
    private static final int HOUR = 60;
    private static final int CLEAN_TIME = 10; // 청소시간

    public static int solution(String[][] book_time) {
        int answer = 0;

        int[] rooms = new int[MAX_TIME];

        for (String[] time : book_time) {
            String inTime = time[0];
            String outTime = time[1];

            rooms[calTime(inTime)] += 1; // 입실 시간
            /*
              끝+1을 하지 않는 것은 seeminglyjs님의 질문에 대한 댓글을 참고해 주세요!
            */
            rooms[calTime(outTime) + CLEAN_TIME] += -1; // 퇴실 + 청소 시간
        }

        // 누적합
        for (int i = 1; i < MAX_TIME; i++) {
            rooms[i] += rooms[i-1];
            answer = Math.max(answer, rooms[i]);
        }

        return answer;
    }

    private static int calTime(String time){
        String[] split = time.split(":");
        String hour = split[0];
        String minute = split[1];
        return ((Integer.parseInt(hour) * HOUR) + Integer.parseInt(minute));
    }
}