[프로그래머스/Lv.2] 호텔 대실 - Java

문제

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

프로그래머스

 

배열 book_time에 저장된 각 예약 건의 입실 시간과 퇴실 시간을 바탕으로 최소 몇 개의 객실이 필요한지 구하는 문제이다. 퇴실 시간 이후 청소 시간 10분 동안은 다른 예약자가 같은 방을 사용할 수 없다는 점을 고려해야 한다.

 

 

리뷰

풀이

먼저 편하게 시간을 계산하기 위해 입실 시간과 퇴실 시간을 필드로 갖는 클래스 BookTime을 만들었다. 그리고 book_time의 각 원소들을 BookTime 형태로 변환하여 리스트로 저장했다. 입실 시간이 빠른 예약 건부터 처리해야 하므로 해당 리스트를 입실 시간이 빠른 순으로 정렬했다.

 

현재 방을 사용하고 있는 예약 건을 저장하기 위해 큐를 활용하면 된다고 생각했다. 특히 항상 퇴실 시간이 빠른 순으로 유지해야 한다는 점을 고려하여 우선순위 큐를 사용했다.

 

기본적인 로직은 다음과 같다.

1. 방은 최소 한 개 이상 필요하다.
2. 입실 시간 순으로 정렬된 리스트에서 예약 건을 순서대로 꺼내 처리한다.
3. 큐가 비어 있다면 해당 예약 건을 추가한다. 이때 방은 추가로 필요하지 않다.
4. 큐에 객체가 있다면 리스트의 예약 건과 큐의 예약 건(퇴실 시간이 가장 빠른 예약 건)을 비교한다.
   • 리스트 예약 건의 입실 시간이 큐 예약 건의 퇴실 시간(+청소 시간) 이후라면 방을 바로 사용할 수 있다. 따라서 방은 추가로 필요하지 않다.
   • 리스트 예약 건의 입실 시간이 큐 예약 건의 퇴실 시간(+10분) 이전이라면 방을 사용할 수 없다. 따라서 방이 추가로 필요하다.

코드

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

class Solution {

    List<BookTime> bookTimes = new ArrayList<>();

    public int solution(String[][] book_time) {

        int bookNum = book_time.length;

        for(int i = 0;i<bookNum;i++) {
            String[] start = book_time[i][0].split(":"); 
            String[] end = book_time[i][1].split(":");
            BookTime bookTime = new BookTime(start[0], start[1], end[0], end[1]);

            bookTimes.add(bookTime);
        }

        Collections.sort(bookTimes, Comparator.comparing(v -> v.start));

        int room = 1;

        // 퇴실 시간이 빠른 순으로 유지하는 우선순위 큐 생성
        Queue<BookTime> now = new PriorityQueue<>(Comparator.comparing(v->v.end));

        for (int i=0;i<bookNum;i++) {
            BookTime cur = bookTimes.get(i);

            if (now.isEmpty()) {
                now.offer(cur);
            }
            else{
                BookTime target = now.peek();

                if (target.isCheckedOut(cur)) {
                    now.poll();
                    now.offer(cur);
                }
                else{
                    room+=1;
                    now.offer(cur);
                }
            }
        }

        return room;
    }
}

class BookTime {

    public LocalTime start;
    public LocalTime end;

    BookTime (String sh, String sm, String eh, String em) {
        this.start = LocalTime.of(Integer.parseInt(sh), Integer.parseInt(sm));
        this.end = LocalTime.of(Integer.parseInt(eh), Integer.parseInt(em));
    }

    public boolean isCheckedOut(BookTime cur) {
        if(this.end.plusMinutes(10).compareTo(cur.start) <= 0){
            return true;
        }

        return false;
    }
}