프로그래머스 호텔 대실 자바 풀이

문제 링크

문제 요약

예약 시간이 담긴 2차원 배열 book_time이 주어진다
퇴실 후 10분간 청소를 해야 다음 손님을 받을 수 있다
필요한 최소 객실 수를 구한다

문제 풀이

처음에는 예약을 시간 순으로 정렬한 뒤, 새 예약이 들어올 때마다 이미 사용 중인 객실을 하나씩 비교해서 겹치지 않는 방이 있는지 확인하면 되겠다고 생각했다.

하지만 이 방식은 비효율적이다.

book_time의 길이가 최대 1,000인데, 예약마다 사용 중인 방 목록을 전부 훑으면 최악의 경우 비교 횟수가 100만에 가까워진다.

이 문제의 핵심은 우선순위 큐에 방이 다시 비는 시각만 담아 두고, 가장 빨리 비는 방부터 확인한다는 점이다.

예약을 시작 시각 기준으로 정렬한 뒤, 우선순위 큐에서 가장 먼저 빌 시각을 꺼내 본다.

그 시각이 새 예약의 시작 시각보다 같거나 이르면 그 방을 재사용할 수 있으므로 큐에서 제거한다.

그리고 새 예약의 퇴실 시각에 청소 시간 10분을 더한 값을 다시 큐에 넣는다.

이때 방을 재사용하지 못했다면 새 방을 하나 더 써야 하므로, 큐의 크기가 곧 그 시점까지 필요했던 객실 수가 된다.

매 예약마다 큐의 크기 중 최댓값을 답으로 갱신하면 된다.

최종 코드

java

import java.util.*;

class Solution {
    public int toMin(String time){
        int h = Integer.parseInt(time.substring(0,2));
        int m = Integer.parseInt(time.substring(3));
        
        return h*60+m; // 시:분을 분 단위로 환산
    }
    
    public int solution(String[][] book_time) {
        int answer = 1;
        int n = book_time.length;
        int[][] time = new int[n][2];
        
        for(int i=0;i<n;i++){
            time[i][0] = toMin(book_time[i][0]);
            time[i][1] = toMin(book_time[i][1]);
        }
        
        // 시작 시각 기준으로 정렬, 같으면 종료 시각 기준
        Arrays.sort(time, (o1,o2)->{
            if(o1[0]==o2[0])
                return Integer.compare(o1[1], o2[1]);
            return Integer.compare(o1[0], o2[0]);
        });
        
        PriorityQueue<Integer> pq = new PriorityQueue<>(); // 각 방이 다시 비는 시각(청소 시간 포함)
        
        pq.add(time[0][1]+10);
        
        for(int i=1;i<n;i++){
            // 가장 빨리 비는 방이 현재 예약 시작 전에 준비되면 재사용
            if(pq.peek() <= time[i][0]){
                pq.poll();
            }
            
            pq.offer(time[i][1]+10);
            
            answer = Math.max(answer, pq.size()); // 그 시점까지 필요했던 최대 객실 수
        }
        
        return answer;
    }
}

호텔 대실

문제 요약

문제 풀이

최종 코드

함께 읽으면 좋은 글

택배상자

롤케이크 자르기

할인 행사

숫자 변환하기