[프로그래머스] 호텔 대실 Lv2 JAVA [우선순위큐][엄탱]

비슷한 문제 풀이 링크

[프로그래머스] 과제 진행하기 Lv2 JAVA [우선순위큐][엄탱]

문제 링크

프로그래머스

문제 설명

호텔을 운영 중인 코니는 최소한의 객실만을 사용하여 예약 손님들을 받으려고 합니다.
한 번 사용한 객실은 퇴실 시간을 기준으로 10분간 청소를 하고 다음 손님들이 사용할 수 있습니다.
예약 시각이 문자열 형태로 담긴 2차원 배열 book_time이 매개변수로 주어질 때, 코니에게 필요한 최소 객실의 수를 return 하는 solution 함수를 완성해 주세요.

해설

저번에 풀었던 문제와 비슷한 종류의 문제여서 우선순위큐로 풀면 쉽게 풀릴 거라고 판단했다.

하지만, 다른 분들의 풀이를 보고 재밌는 풀이가 보여서 두 가지 해설을 준비했다.

1. PriorityQueue를 이용한 방법(우선순위큐)

역시나 우선순위큐에서 중요한 것은 정렬이다. 

어떤 기준을 갖고 정렬을 하는지가 중요하다고 판단된다.

여기서 우선순위 큐는 이미 사용 중인 대실들의 리스트라고 생각하면 좋다.

1. book_time을 대실 시작 시간 기준으로 오름차순 해준다.
2. PriorityQueue는 대실 종료 시간 기준으로 오름차순 해준다.
   • 가장 빨리 비어지는 방과 그다음 들어올 대실 시작 시간과 비교하기 위함이다.
   • 가장 빨리 비어지는 방만 비교해 보면 그다음 방들은 어차피 시간이 안되기 때문에 비교할 필요가 없어진다.

이렇게 준비해 주고 아래 프로세스와 같이 진행하면 된다.

1. book_time을 정말 탐색하여 대실의 시작, 종료 시간을 분으로 변경해 주고 10분을 더해준다.
2. book_time에서 가장 빨리 시작하는 대실의 시작 시간과 우선순위큐 첫 번째 종료시간과 비교하자
   • 대실 시작시간이 우선순위큐(사용 중인 대실들) 첫 번째 종료시간보다 크면 대실을 우선순위 큐에 넣어주고 방 개수를 추가해준다.
   • 반대로 작으면 우선순위큐(사용 중인 대실들) 첫 번째 값을 빼고 대실을 우선순위 큐에 넣어주고 방 개수는 그대로 둔다.
   • 사용중인 대실들이 없으면 대실을 넣어주고 방 갯수 추가 해준다.
3. 최종 방 갯수 반환

코드

import java.util.*;

class Solution {
    public int solution(String[][] book_time) {
        int answer = 0;

        Arrays.sort(book_time, (x, y) -> x[0].compareTo(y[0]));

        PriorityQueue<int[]> pq = new PriorityQueue<>((x, y) -> x[1] - y[1]);

        for (String[] book: book_time) {
            String[] starts = book[0].split(":");
            String[] ends = book[1].split(":");
            
            int start = Integer.parseInt(starts[0]) * 60 + Integer.parseInt(starts[1]);
            int end = Integer.parseInt(ends[0]) * 60 + Integer.parseInt(ends[1]) + 10;
            
            if (pq.isEmpty()) {
                answer++;
                pq.offer(new int[]{start, end});
                continue;
            } 
            
            int[] prev = pq.poll();
            
            int prevStart = prev[0];
            int prevEnd = prev[1];
            
            if (start >= prevEnd) {
                pq.offer(new int[]{start, end});
            } else {
                answer++;
                pq.offer(new int[]{start, end});
                pq.offer(prev);
            }
        }

        return answer;
    }
}

2. 다른 방법(DP?)

이 방법은 간단하게 설명하겠다.

1. 배열을 하나 준비한다.
   • 예약된 방들의 사용 시간들을 체크해 주기 위한 배열
2. 예약 시작 시간과 종료 시간을 분으로 변경해준다.
3. 준비된 배열에 예약 시작 시간부터 종료 시간까지 +1을 해준다
4. 준비된 배열에서 최댓값을 반환한다.

이렇게 하게 되면 겹치는 방들을 전부 파악할 수 있게 된다. 

그림으로 한번 살펴보자

색상 칸이 예약 시간이고, 숫자가 현재 사용된 방 숫자라고 생각하면 된다.

예시1

예시2

코드(다른 분 코드)

import java.util.*;

class Solution {
    public int solution(String[][] book_time) {
        int answer = 0;
        int[] arr = new int[1440];
        for(String[] book : book_time){
            int start = changeMin(book[0]);
            int end = Math.min(1439, changeMin(book[1])+10);
            for(int j=start; j<end; j++){
                arr[j]++;
            }
        }
        for(int i=0; i<1440; i++){
            answer = Math.max(answer, arr[i]);
        }
        return answer;
    }

    public int changeMin(String time){
        int h = Integer.parseInt(time.split(":")[0]);
        int m = Integer.parseInt(time.split(":")[1]);
        int min = h * 60 + m; 
        return min;
    }
}