우선순위 큐 (1) - 호텔 대실

문제

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

 

 

풀이

객실의 입실, 퇴실 시간을 고려하여 최소한으로 배정되는 방의 수를 찾는 문제였다.

어려웠던 부분은, 우선순위 큐에 Comparator를 커스텀하여 내부의 시간을 정렬하는 것과, 날짜의 연산(DateType, DateFormat)이 어려웠다.

 

1. 우선 순위 큐의 정렬을 커스텀 해야한다.

PriorityQueue<String[]> pq = new PriorityQueue<>(Comparator.comparing(a -> a[0]));

 

해당 큐에는 [입실 시간, 퇴실 시간]으로 이루어진 배열이 들어있다.

 

 

2. 모든 방의 입실 가능한 시간은 앞 예약자의 퇴실 시간 + 10분(청소시간) 이다.

dList.add(new Date(df.parse(pq.poll()[1]).getTime() + (10 * 60 * 1000)));

 

10분을 더하는 방법을 잘 몰라 많이 헤맸다.

 

 

3. hh:mm은 12시가 00시로 나와 비교 구문에서 오류가 생긴다. 그러므로 HH:mm으로 해주어야 정확한 시간 비교가 가능하다.

SimpleDateFormat df = new SimpleDateFormat("HH:mm");

 

이 부분에서 가장 많이 헤맸던 것 같다. 사소한 오류였지만, 중요한 오류였다.

 

 

4. 방의 입실 시간과, 퇴실 시간을 비교하면서 조건을 만족하는 방이 있다면 해당 퇴실 시간 + 10분의 시간을 배열에 넣어 갱신해주고, 없다면 array의 size를 하나 늘려준다. (방을 늘려준다.)

int size = dList.size();
for (int i = 0; i < size; i++) {
    Long newDate = time[1].getTime() + (10 * 60 * 1000);
    if (dList.get(i).getTime() <= time[0].getTime()) {
        dList.set(i, new Date(newDate));
        break;
    }
    if (i == dList.size() - 1) {
        dList.add(new Date(newDate));
    }

 

처음에 size를 그대로 조건문에 넣었다가 무한 루프가 일어났다. size의 크기를 저장해준 뒤 넣도록 해야한다.

 

 

전체 코드

import java.io.IOException;
import java.text.ParseException;
import java.text.SimpleDateFormat;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.Date;
import java.util.PriorityQueue;

class Solution {
    public static int solution(String[][] book_time) throws ParseException {
        int answer = 0;
        ArrayList<Date> dList = new ArrayList<>();
        PriorityQueue<String[]> pq = new PriorityQueue<>(Comparator.comparing(a -> a[0]));
        for (int i = 0; i < book_time.length; i++) {
            pq.offer(book_time[i]);
        }
        SimpleDateFormat df = new SimpleDateFormat("HH:mm");
        dList.add(new Date(df.parse(pq.poll()[1]).getTime() + (10 * 60 * 1000)));

        while (!pq.isEmpty()) {
            String[] date = pq.poll();
            Date[] time = {df.parse(date[0]), df.parse(date[1])};
            int size = dList.size();
            for (int i = 0; i < size; i++) {
                Long newDate = time[1].getTime() + (10 * 60 * 1000);
                if (dList.get(i).getTime() <= time[0].getTime()) {
                    dList.set(i, new Date(newDate));
                    break;
                }
                if (i == dList.size() - 1) {
                    dList.add(new Date(newDate));
                }
            }
        }
        answer = dList.size();
        return answer;
    }
}