[프로그래머스/Java] 호텔 대실 - Level 2

프로그래머스

 

 

• 문제

입력으로 호텔을 예약하는 사람들의 "시작 시간", "종료 시간"이 String 배열로 주어진다.

 

운영자는 시작 시간과 종료 시간이 겹치는 사람의 최대 수 만큼 객실을 운영하여 비용을 최소로 하려고 한다. 겹치는 고객의 최대 수를 구해보자.

 

• 풀이

문제를 보자마자 생각한 방법은 dp인가? 누적합인가? 하는 방식이다.

 

입력은 HH:MM으로 주어지고 최대 시간은 23:59이다. 이를 int형으로 바꾸면 HH*60+MM으로 최대로 가질 수 있는 int 값은 1439이지만 청소 시간을 추가해야한다. 청소시간은 10분으로 10을 더한 값인 1449가 최대로 가질 수 있는 시간 값으로 볼 수 있다. 여기서 시간값은 배열의 인덱스로 가질 수 있는 값임을 인지했다. 

 

먼저 String 배열을 한바퀴 돌며 int형 배열에 시작 시간 index에 +1, 종료시간 +10한 값에 -1을 하면 배열을 한 바퀴 돌 때 겹치는 고객의 최대 수를 구할 수 있을 것이라고 판단했다.

 

파단해본 알고리즘으로 문제를 가정해보자. 아래 "시작 시간", "종료시간 + 청소시간"을 가진 고객 4명이 주어졌다.

"1", "9"

"2", "8"

"3", "7"

"7", "9"

아래는 위 의 4개의 고객이 존재할 때, 구현된 표이다.

index	1	2	3	4	5	6	7	8	9
배열 값	1	1	1	0	0	0	0	-1	-2
누적합	1	2	3	3	3	3	3	2	0

index 3부터 고객 3명이 함께 사용할 때 누적합의 값이 3을 가진다. index 7 때는 종료 고객 1명, 시작 고객 1명이 겹쳐서 고객 3명이 그대로 유지하는 모습이다.

 

이처럼 판단한 알고리즘 대로 구현하면 O(1440) 정도의 시간으로 문제를 정확하게 풀어낼 수 있다.

 

• 풀이

class Solution {
    public int solution(String[][] book_time) {
        int answer = 0;
        int[] dp = new int[1450];
        for(int i = 0; i < book_time.length; i++) {
            int start_time = getStringToTime(book_time[i][0]);
            int end_time = getStringToTime(book_time[i][1])+10;
            dp[start_time]++;
            dp[end_time]--;
        }
        
        for(int i = 1; i <= 1440; i++) {
            dp[i] += dp[i-1];
            answer = Math.max(answer, dp[i]);
        }
        return answer;
    }
    
    public int getStringToTime(String s) {
        String[] t = s.split(":");
        return Integer.parseInt(t[0])*60+Integer.parseInt(t[1]);
    }
}