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

문제를 보자마자 누적합을 이용하면 쉽게 풀수 있을것이라고 생각했다.

다만, 누적합을 어떻게 구현해야 하는지 잘 생각이 나지 않아

LocalTime 클래스를 이용해서 풀어보았으나, 테스트 케이스 통과를 하지 못하였다.

그래서 누적합에 대해 검색했고, 쉽게 풀 수 있었다.

---

로직

2차원 배열 book_time을 순회하며 방 입실 시간과, 퇴실 시간을 구한다.

퇴실 시간에 청소시간을 고려하여 10분을 더해주면 된다.

arr 배열에 모든 입실시간과 퇴실시간을 더해주고, 누적합을 구하며 최댓값을 찾으면 된다.

 

최종 코드

import java.util.*;
class Solution {
    public int solution(String[][] book_time) {
        int answer = 0;
        int[] arr = new int[1450];
        
        // 시 : 분을 분으로 변환 후 int 배열에 넣기
        for(int i = 0; i < book_time.length; i++) {
            int[] startTemp = Arrays.stream(book_time[i][0].split(":"))
                .mapToInt(Integer::parseInt)
                .toArray();
            int startTime = startTemp[0] * 60 + startTemp[1];
            
            int[] endTemp = Arrays.stream(book_time[i][1].split(":"))
                .mapToInt(Integer::parseInt)
                .toArray();
            int endTime = endTemp[0] * 60 + endTemp[1] + 10;
            
            arr[startTime] += 1;
            arr[endTime] += -1;
        }
        
        // 누적합 계산 및 최댓값 찾기
        for(int i = 1; i < arr.length; i++) {
            arr[i] += arr[i - 1];
            answer = Math.max(answer, arr[i]);
        }
        
        return answer;
    }
}