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

누적합 (Cumulative Sum)

주어진 배열 또는 리스트의 각 요소까지의 누적된 합을 구하는 것

누적합은 배열의 원소를 한 번씩 순회하며 이전 요소들까지의 합을 누적하여 저장하는 방식으로 계산

이렇게 누적된 합을 이용하면 배열 내의 어떤 부분 배열의 합을 빠르게 계산할 수 있음

 

예) 원본 배열: [1, 2, 3, 4, 5]            누적합: [1, 3, 6, 10, 15]

 

누적합 시간복잡도 : 배열의 길이가 N일 때 O(N)

프로그래밍에서는 주로 누적합을 이용하여 특정 구간의 합을 빠르게 구하는 등의 연산에 활용

누적합을 사용하면 반복적으로 부분 배열 합을 계산하는 경우에 비해 더 효율적인 알고리즘을 설계할 수 있음

 

 

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

프로그래머스

 

 

내 답안 : 

 

class Solution {
    //고정 상수 선언
    private static final int MAX_TIME = 1450;    
    //1440(60분*24시간)+10(청소시간)
    private static final int HOUR = 60;
    private static final int TIME_FOR_CLEANING = 10;
    
    //예약 시간을 분 단위로 변환
    private static int calTime(String time) {
        String[] split = time.split(":");
        int hour = Integer.parseInt(split[0]) * 60;
        int min = Integer.parseInt(split[1]);
        return hour + min;
    }
 
    public int solution(String[][] book_time) {
        int answer = 0;
 
        int[] room = new int[MAX_TIME];
        
        //for each문 : for(type var : iterate)
        for (String[] time : book_time) {
            String inputTime = time[0];
            String outputTime = time[1];
            
            // 겹치는 예약 수 누적 계산
            room[calTime(inputTime)] += 1;
            room[calTime(outputTime) + TIME_FOR_CLEANING] -= 1;
        }
 
        // 가장 큰 room[i] 값이 필요한 방의 최대 갯수
        for (int i = 1; i < MAX_TIME; i++) {
            room[i] += room[i - 1];
            answer = Math.max(answer, room[i]);
        }
        return answer;
    }
}

 

시간복잡도 :  O(N) (N = book_time 배열의 크기) 

 

 

이 문제의 경우 누적합으로 풀이하는 것이 가장 속도가 빠름