[pro] 프로그래머스 level2 155651 호텔 대실 (Java) - 누적합

[문제]

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

프로그래머스

 

[풀이]

배열 누적합 문제.

입실시간과 퇴실시간을 분으로 환산한 후 배열에 기록하여 누적합을 하면 특정 시간대에 사람들이 얼마나 겹치는 지를 알 수 있다. 가장 많이 겹치는 만큼 방이 필요하므로 이를 갱신해주면 된다.

 

배열 누적합에 대해서는 따로 알고리즘 정리글을 쓸 생각이지만, 간단하게 정리해보면 다음과 같다.

[2, 6], [4, 8] 두 배열에 대해서 공간을 채운다고 하면 for문을 돌며 일일이 count를 증가시키는 방법으로 할 수 있다. 그러나 여러개의 배열이 누적으로 더해질 때 위와 같은 방법을 효율적이지 않기 때문에 다음의 방법을 사용할 수 있다.

배열의 시작 위치에 +1을, 배열이 끝나는 위치+1 위치에 -1을 기록해준다.

 

0	1	2	3	4	5	6	7	8	9
0	0	+1	0	+1	0	0	-1	0	-1

 

그리고 하나의 for문을 돌면서 누적합을 해준다.

 

for(int i=1; i<arr.length; i++){
	arr[i] += arr[i-1];
}

 

0	1	2	3	4	5	6	7	8	9
0	0	+1	+1	+2	+2	+2	+1	+1	0

 

따로 반복문을 돌며 배열을 채운 것과 같은 누적 배열을 얻을 수 있다!

 

[코드]

 

import java.util.*;

class Solution {
    public int solution(String[][] book_time) {
        int answer = 0;
        //코니에게 필요한 최소 객실의 수를 return 
        
        int[] rooms =  new int[60*24+10];
        
        for(String t[]:book_time){
            int s = stringToInt(t[0]);
            int e = stringToInt(t[1])+10; //분으로 변환
            
            rooms[s] += 1;
            rooms[e] -= 1;
        }
        
        for(int i=1; i<60*24+10; i++){
            rooms[i] += rooms[i-1];
            answer = Math.max(rooms[i], answer);
        }
        
        return answer;
    }
    
    static int stringToInt(String time){
        int hour = Integer.parseInt(time.substring(0, 2));
        int min = Integer.parseInt(time.substring(3, time.length()));
        
        return hour*60+min;
    }
    
    
}