[Programmers] 155651. 호텔 대실(누적합)

• 성능 요약
• 구분
• Answer Code1(23.10.24)
• 문제 풀이
• Review
• Reference

문제 링크

성능 요약

• 메모리: 79.2 MB, 시간: 3.52 ms

구분

• 코딩테스트 연습 > 연습문제 > 호텔 대실(누적합)

Answer Code1(23.10.24)

import java.util.*;


class Solution {
    public int solution(String[][] book_time) {
        int answer = 1;
        int[] timeCheck = new int[24*60+10];

        for (int i=0; i<book_time.length; i++) {
            int start = convertTime(book_time[i][0].split(":"));
            int end = convertTime(book_time[i][1].split(":"));
            timeCheck[start] += 1;
            timeCheck[end+10] -= 1;
        }
        for (int i=1; i<timeCheck.length; i++) {
            timeCheck[i] += timeCheck[i-1];
            if (answer < timeCheck[i]) {
                answer = timeCheck[i];
            }
        }
        return answer;
    }

    public int convertTime(String[] time) {
        int hour = Integer.parseInt(time[0]);
        int min = Integer.parseInt(time[1]);
        return (hour * 60) + min;
    }
}

문제 풀이

• (시간 * 60분 * 10분)으로 전체 시간을 분으로 변환해주고 입실 ~ 퇴실 범위에 값을 누적해주면 된다.

• 다만 매번 입실 ~ 퇴실 시간의 범위에 반복문을 돌려 값을 누적하기엔 시간복잡도가 증가한다.

• 입실 시간에는 +1, 퇴실 시간에는 -1의 값을 대입해 준 뒤 배열을 누적합 해주고 최대값을 반환하면 된다.

• 입실 시간에 +1을 해주는 이유:

  • 객실에 입실하는 순간, 해당 시간대에 새로운 손님이 추가되는 것이기 때문에 해당 시간대의 예약 갯수를 1 증가시킨다.

• 퇴실 시간에 -1을 해주는 이유:

  • 객실을 퇴실하는 순간, 해당 시간대의 손님이 떠나는 것이므로 해당 시간대의 예약 갯수를 1 감소시킨다.

• 누적합(Prefix Sum)

  • timeCheck 배열에 대해 누적합을 계산합니다. 이렇게 함으로써, 각 시간대별로 현재까지 사용 중인 객실의 수를 알 수 있다.

Review

• 누적합에 대한 개념과 전체 시간을 분으로 변환해서 구하는 방법에 대한 로직을 제대로 떠올리지 못했다.

• 해당 문제는 자주 접하지 않더라도, 나중에 다시한번 복습을 통해 제대로 알고 가자.

Reference

• https://ahlight.tistory.com/102