프로그래머스 호텔 대실 문제 - 타임라인 배열로 예약 겹치는 예약 수 계산하기 Java 풀이

문제 설명

프로그래머스 호텔 대실 문제

 

https://school.programmers.co.kr/learn/courses/30/lessons/155651?language=java

프로그래머스

 

 

문제 접근

• 시작 시간과 종료 시간을 바탕으로 하루 동안 겹치는 예약의 최대 개수를 찾아내야한다.
• 예약시간을 HH:MM에서 MM으로 변경하고 그걸 배열 인덱스로 활용하여 시작 시간에 +1, 종료 시간에는 -1을 기록한다.
• 예약 겹침 시간 계산: 시작, 종료시간을 기록한 배열을 순차 탐색하며 누적 합을 계산하면 된다.

예약 겹침 시간 계산하는 부분

        // 타임라인을 사용하여 예약이 겹치는 시간 계산
        int[] timeline = new int[1440 + 10]; // 하루는 최대 1440분, 청소 시간을 고려하여 여유를 둠

        // 각 예약에 대해 시작 시간과 종료 시간에 타임라인 변화 기록
        for (int[] time : times) {
            int start = time[0]; // 시작 시간
            int end = time[1];   // 종료 시간 (청소시간 포함)

            // 시작 시점 +1, 종료 시점 -1
            timeline[start]++;
            timeline[end]--;
        }

        // 타임라인을 바탕으로 겹치는 예약의 최대 개수 찾기
        int maxOverlap = 0;
        int currentOverlap = 0;

        for (int i = 0; i < 1440; i++) {
            currentOverlap += timeline[i]; // 겹치는 예약 수 계산
            maxOverlap = Math.max(currentOverlap, maxOverlap); // 최대 겹치는 예약 수 찾기
        }

전체 코드

class Solution {
    public int solution(String[][] book_time) {
        int answer = 0;
        int row = book_time.length;
        int[][] times = new int[row][2];
        
        for(int i = 0; i < row; i++) {
            for (int j = 0; j < 2; j++) {
                String[] timeParts = book_time[i][j].split(":");
                int hours = Integer.parseInt(timeParts[0]);
                int minutes = Integer.parseInt(timeParts[1]);
                
                if (j == 1) {
                    times[i][j] = hours * 60 + minutes + 10; // 청소 시간 고려    
                } else {
                    times[i][j] = hours * 60 + minutes;
                }
            }
        }
        
        int[] timeline = new int[1440 + 10]; //하루는 최대 1440분 + 청소 시간 10분 추가
        
        for (int[] time : times) {
            int start = time[0];
            int end = time[1];
            
            timeline[start]++;
            timeline[end]--;
        }
        
        int maxOverlap = 0;
        int currentOverlap = 0;
        
        for (int i = 0; i < 1440; i++) {
            currentOverlap += timeline[i];
            maxOverlap = Math.max(currentOverlap, maxOverlap);
        }
        return maxOverlap;
    }
}