[프로그래머스] 호텔 대실 - Java

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/155651

문제 설명

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

제한사항

알고리즘: 우선순위 큐

풀이

먼저 예약 시각을 기준으로 오름차순 정렬해 준다. (비교에 용이하게 분으로 변환해서 저장함)
방은 최소한으로 사용하는 게 목적이기 때문에 새로운 방을 대실 하는 것 보다 기존 사용한 방을 최대한 사용해야 한다. 우선순위를 매겼을 때 1. 기존 사용한 방, 2. 새로운 방이다.

그러면 기존 사용한 방이 끝났는지를 체크해 줘야 한다. 체크를 해줄 때 사용 중인 모든 방을 체크해 줄 필요가 없다. 사용 중인 방중에 대실 종료 시각이 제일 빠른 방만 체크해 주면 된다. 그렇기 때문에 대실 종료 시각이 빠른 방을 우선으로 하는 우선순위 큐를 사용한다.

이제 대실 시각을 오름차순으로 정렬한 book_time을 차례대로 확인하는데, 대실 시각이 우선순위 큐에 첫 번째 값보다 크거나 같다면 해당 방에 입실할 수 있다. 그렇지 않다면 새로운 방에 입실한다. 모든 book_time을 확인했다면 우선순위 큐에 size가 코니에게 필요한 최소 객실의 수가 된다.

소스 코드

import java.util.*;
class Solution {
    static int[][] book_t;
    static PriorityQueue<Integer> priorityqueue = new PriorityQueue<>();
    public int solution(String[][] book_time) {
        int answer = 0;
        book_t = new int[book_time.length][book_time[0].length];
        for(int i=0; i<book_time.length; i++) {
            for(int j=0; j<book_time[i].length; j++) {
                StringTokenizer st = new StringTokenizer(book_time[i][j], ":");
                int min = Integer.parseInt(st.nextToken()) * 60 + Integer.parseInt(st.nextToken());
                book_t[i][j] = min;
            }
        }
        Arrays.sort(book_t, (a,b) -> {
            return a[0] - b[0];
        });
        for(int i=0; i<book_t.length; i++) {
            if(i==0) priorityqueue.add(book_t[i][1] + 10);
            else {
                if(book_t[i][0] >= priorityqueue.peek()) {
                    priorityqueue.remove();
                    priorityqueue.add(book_t[i][1] + 10);
                } else priorityqueue.add(book_t[i][1] + 10);
            }
        }
        answer = priorityqueue.size();
        return answer;
    }
}