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

문제

호텔을 운영 중인 코니는 최소한의 객실만을 사용하여 예약 손님들을 받으려고 합니다.

한 번 사용한 객실은 퇴실 시간을 기준으로 10분간 청소를 하고 다음 손님들이 사용할 수 있습니다.
예약 시각이 문자열 형태로 담긴 2차원 배열 book_time이 매개변수로 주어질 때, 코니에게 필요한 최소 객실의 수를 return 하는 solution 함수를 완성해주세요.

풀이

처음엔 시작 시간과 끝 시간을 저장을 해야 하는 자료구조가 있어야 한다고 생각했다.
따라서 시작시간을 key, 끝시간을 value로 하는 map을 이용해서 이를 저장하려고 했다.
후에 시작시간과 끝 시간을 비교하면서 겹치는 시간때일때 값을 증가 시키는 로직으로 구현했는데 오류가 발생했다.
MAX값을 제대로 구하지 못하는 문제였다. 입력 순서에 따라서 if를 통과여부가 달라지고 정렬을 시키더라도 아마 시간이 많이 걸려서 시간초과가 날것이라고 생각했다.

따라서 다른 방법을 찾으면서 누적합을 이용한 방법을 알아냈다.
덕분에 누적합을 알아보는 계기가 되었다... 오히려좋아!
hours배열이 00시부어 24시까지 모조리 분으로 계산한 배열이다.
따라서 hours배열에 숫자가 가장 큰 수가 있으면 그 시간대에서 방이 제일 많이 필요한 시간대 이므로 그 갯수만큼의 방만을 확보하면 된다.

import java.util.*;
import java.lang.*;

class Solution {
    static final int CLEANTIME = 10;
    static final int HOUR = 60;
    static final int MAXTIME = 1450;
    public int solution(String[][] book_time) {
        int answer = 1;
        int[] hours = new int[MAXTIME];
        for(int i = 0; i < book_time.length; i++) {
            String[] startTime = book_time[i][0].split(":");
            String[] endTime = book_time[i][1].split(":");

            hours[Integer.parseInt(startTime[0]) * HOUR + Integer.parseInt(startTime[1])] += 1;
            hours[Integer.parseInt(endTime[0]) * HOUR + Integer.parseInt(endTime[1]) + CLEANTIME] -= 1;
        }

        //누적합 구하기
        for(int i = 1; i < MAXTIME; i++) {
            hours[i] += hours[i - 1];
            answer = Math.max(answer, hours[i]);
        }


        return answer;
    }
}

https://github.com/Win-9/Algorism/tree/main/programers/%ED%98%B8%ED%85%94%EB%8C%80%EC%8B%A4