프로그래머스 - 호텔 대실 (Java, 자바)

문제 링크

문제 설명

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

---

제한사항

• 1 ≤ book_time의 길이 ≤ 1,000
  • book_time[i]는 ["HH:MM", "HH:MM"]의 형태로 이루어진 배열입니다
    • [대실 시작 시각, 대실 종료 시각] 형태입니다.
  • 시각은 HH:MM 형태로 24시간 표기법을 따르며, "00:00" 부터 "23:59" 까지로 주어집니다.
    • 예약 시각이 자정을 넘어가는 경우는 없습니다.
    • 시작 시각은 항상 종료 시각보다 빠릅니다.

---

입출력 예

book_time	result
[["15:00", "17:00"], ["16:40", "18:20"], ["14:20", "15:20"], ["14:10", "19:20"], ["18:20", "21:20"]]	3
[["09:10", "10:10"], ["10:20", "12:20"]]	1
[["10:20", "12:30"], ["10:20", "12:30"], ["10:20", "12:30"]]	3

 

---

입출력 예 설명

입출력 예 #1

위 사진과 같습니다.

입출력 예 #2

첫 번째 손님이 10시 10분에 퇴실 후 10분간 청소한 뒤 두 번째 손님이 10시 20분에 입실하여 사용할 수 있으므로 방은 1개만 필요합니다.

입출력 예 #3

세 손님 모두 동일한 시간대를 예약했기 때문에 3개의 방이 필요합니다.

---

문제 풀이 과정

1. 문자열로 된 시간을 분으로 변경한다. 이때 종료 시간에는 청소 시간 10분을 포함하여 저장한다.
2. 예약 시간이 빠른 순으로 배열을 정리하며, 예약 시간이 같을 경우 종료 시간을 기준으로 정렬한다.
3. 우선순위큐를 이용하여 종료시간을 관리한다.
4. 우선순위큐에 있는 값보다 시작 시간이 빠를 경우 새로운 방이 필요하다.
5. 우선순위큐에 있는 값보다 시작 시간이 늦을 경우 해당 방에 예약이 가능 하므로 우선순위큐에 있는 값을 빼고 새로운 값을 넣는다.
6. 우선순위큐의 크기가 필요한 방의 크기가 된다.

2번 과정을 예약 종료 시간순으로 했었는데 예시 테스트 3개 보두 통과 되지만 제출 했을 때 3가지 테스트만 통과 되고 나머지 테스트에서는 통과 되지 않았다.
이것을 시작 시간 순으로 정렬로 변경하였더니, 보든 테스트 케이스에서 통과가 되었다.

---

전체 코드

import java.util.*;

class Solution {
    public int solution(String[][] book_time) {
        int[][] booking = new int[book_time.length][2];

        //시간을 분으로 변경
        for (int i = 0; i < book_time.length; i++) {
            String[][] temp = new String[2][2];
            temp[0] = book_time[i][0].split(":");
            temp[1] = book_time[i][1].split(":");

            booking[i][0] = Integer.parseInt(temp[0][0]) * 60 + Integer.parseInt(temp[0][1]);
            booking[i][1] = Integer.parseInt(temp[1][0]) * 60 + Integer.parseInt(temp[1][1]) + 10;
        }

        Arrays.sort(booking, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[0] == o2[0]){
                    return o1[1] - o2[1];
                }
                return o1[0] - o2[0];
            }
        });

        PriorityQueue<Integer> pq = new PriorityQueue<>();

        for (int i = 0; i < booking.length; i++) {
            if(!pq.isEmpty()) {
                if (pq.peek() <= booking[i][0]) {
                    pq.poll();
                }
            }
            pq.add(booking[i][1]);
        }

        return pq.size();
    }
}