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

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

프로그래머스

 

문제 풀이

매번 회의실 문제 같은 거 보면 머리아팠는데 누적합 알고리즘으로도 풀 수 있다는 걸 알고 바로 활용했다.

 

가능한 모든 시간대 timeTable에 강의되고 있는 시간대를 증가시킨다. 그 중 최댓값이 필요한 최소한의 강의실이다.

 

하지만 단순히 반복문으로 book_time에서 가져온 값을 그대로 시간대를 증가시키면 시간초과가 발생하기 때문에 누적합 알고리즘을 적용해야 한다.

 

코드

import java.util.*;
class Solution {
    static final int MAX_TIME = 24*60+10;
    
    static int hToM(int h, int m){
        if(m>=60){
            h++;
            m-=60;
        }
        return h*60+m;
    }
    
    public int solution(String[][] book_time) {
        int[] timeTable= new int[MAX_TIME];
        
        // timeTable 초기화
        for(int i=0; i<book_time.length; i++){
            int startTime[] = Arrays.stream(book_time[i][0].split(":"))
                    .mapToInt(Integer::parseInt)
                    .toArray();
            int startM = hToM(startTime[0], startTime[1]);

            int endTime[] = Arrays.stream(book_time[i][1].split(":"))
                    .mapToInt(Integer::parseInt)
                    .toArray();
            int endM = hToM(endTime[0], endTime[1]+10);

            timeTable[startM]++;
            timeTable[endM]--;
        }
        
        int answer=0;
        // 누적합 계산 및 최댓값 찾기
        for(int i=1; i<MAX_TIME; i++){
            timeTable[i]+=timeTable[i-1];
            answer = Math.max(timeTable[i], answer);
        }
        
        return answer;
    }
}