[Programmers] 호텔 대실 JAVA

반응형

728x90

[Programmers] 호텔 대실 - LV 2

---

접근

• 그리디

---

풀이

오랜만의 프로그래머스 문제이다. 호텔 대실이라는 문제로 대실에 대한 시작 시간과 종료 시간이 주어지고 모든 예약 처리를 위해 최소 몇 개의 방이 필요한 지 구하는 문제이다. 특이 사항으로 대실이 종료된 후 청소 시간이 존재하기 때문에 종료 후 10분간은 청소를 위해 대실이 제한된다. 

    public int solution(String[][] book_time) {
        Arrays.sort(book_time, (a,b) -> a[0].compareTo(b[0]));

        PriorityQueue<LocalTime> endTimeQueue = new PriorityQueue<>();
        
        int result = 1;

우선 예약 관리를 순차적으로 하기 위해 시작 시간을 기준으로 정렬해 줬다. 그리고 종료 시간은 우선순위 큐를 통해 관리하게 된다. result 변수는 필요한 방의 개수를 나타낸다. 

	for (String[] times : book_time) {
            LocalTime startTime = LocalTime.parse(times[0]);
            LocalTime endTime = LocalTime.parse(times[1]);

            while (!endTimeQueue.isEmpty() && endTimeQueue.peek().plusMinutes(9).isBefore(startTime)) {
                endTimeQueue.poll();
            }

            endTimeQueue.offer(endTime);

            if (endTimeQueue.size() > result) {
                result++;
            }
        }

        return result;

시간 계산을 위해 LocalTime을 사용했다. 각 시간을 LocalTime으로 관리하고 루프를 돌며 예약에 접근한다. 시작 시간을 기준으로 순차접근 하기 때문에 다음 예약에 접근하면 먼저 시작 시간과 우선순위 큐에 들어있던 종료 시간들을 비교하여 대실이 끝난 방들을 모두 제거해 준다. 청소시간 10분을 고려해서 비교하게 되는데 20분부터 청소를 시작해 30분에 청소가 끝난다면 바로 30분부터 입실이 가능하기 때문에 10분 대신 9분을 더해 비교해 줬다. 대실이 끝난 모든 방을 제거했으면 현재 예약의 종료 시간을 큐에 넣고 현재 사용한 방의 개수와 큐에 들어있는 예약을 비교해 예약이 현재 방의 개수보다 많다면 필요한 방의 개수를 늘려준다. 

---

청소 시간을 먼저 추가한 뒤 큐에 삽입

처음에 풀 때는 종료 시간에 청소 시간을 먼저 추가한 뒤 큐에 삽입을 했었다. 

	for (String[] times : book_time) {
            LocalTime startTime = LocalTime.parse(times[0]);
            LocalTime endTime = LocalTime.parse(times[1]).plusMinutes(9);

            while (!endTimeQueue.isEmpty() && endTimeQueue.peek().isBefore(startTime)) {
                endTimeQueue.poll();
            }

위 코드처럼 어차피 청소 시간에 대실 시작이 불가능하니 똑같은 거 아닌가 하고 했었다. 저렇게 하면 뒤에 비교하는 코드도 깔끔하고 괜찮지 않을까 했지만 테스트케이스가 실패했다. 왜 그런지 보니 먼저 청소 시간을 더해버리는 경우 자정에 대한 처리가 제대로 이루어지지 않아서였다. 23:59 분에서 청소 시간 9분을 더하는 경우 00:08 분이 되게 되는데 문제는 이게 다음날 00:08분인지 알 수 있는 방법이 없던 것이었다. 그렇게 우선순위 큐에 들어가게 되면 다음날이라는 늦은 시간이지만 날짜를 고려하지 않을 때 가장 우선순위 쪽으로 갈 수밖에 없을 것이고 그렇게 되면 처리가 꼬여버리게 되는 것이다. 그렇다면 자정에 대한 처리 부분을 추가해 주면 되긴 하겠지만 굳이라는 생각이 들어 위의 코드로 처리하는 게 나을 것 같다. 

---

전체 코드

import java.util.*;
import java.time.*;

class Solution {
    public int solution(String[][] book_time) {
        Arrays.sort(book_time, (a,b) -> a[0].compareTo(b[0]));

        PriorityQueue<LocalTime> endTimeQueue = new PriorityQueue<>();
        
        int result = 1;

        for (String[] times : book_time) {
            LocalTime startTime = LocalTime.parse(times[0]);
            LocalTime endTime = LocalTime.parse(times[1]);

            while (!endTimeQueue.isEmpty() && endTimeQueue.peek().plusMinutes(9).isBefore(startTime)) {
                endTimeQueue.poll();
            }

            endTimeQueue.offer(endTime);

            if (endTimeQueue.size() > result) {
                result++;
            }
        }

        return result;
    }
}