[프로그래머스 / 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" 까지로 주어집니다.
    • 예약 시각이 자정을 넘어가는 경우는 없습니다.
    • 시작 시각은 항상 종료 시각보다 빠릅니다.

 

문제 설명

우리의 목표는 가장 적은 방을 사용하여 모든 예약 손님을 받는 것입니다. 현실에서 문제를 어떻게 해결 할 수 있을지를 고민 해 보는 것 역시 문제 해결에 도움이 될 수 있습니다.

 

특정 시간대에 몇 개의 방에는 손님이 묵고 있고, 몇 개의 방은 비어 있는 상황을 가정해 봅시다. 이 때, 새로운 손님이 온다면 이 손님은 이미 비어있는 방 중 어느 방을 선택하더라도 이후의 상황에 차이가 없습니다. 

만약, 새로운 손님이 도착한 상황에서 비어있는 방이 없다면 우리에게는 이 손님을 위한 새로운 방이 하나가 필요합니다.

 

이러한 방법을 고려하여 우리에게 필요한 방의 개수를 구할 수 있습니다.

1. 예약 시간을 대실 시작 시간 기준으로 오름차순 정렬을 한다.
2. 사용 가능한 방의 목록을 우선순위 큐를 이용해 생성한다.
   1. 사용 가능한 시간이 가장 빠른 방의 우선순위가 가장 높다.
3. 정렬된 예약 시간을 확인하며 방의 정보를 변경 한다.
   1. 손님의 대실 시작 시간에 사용 가능한 방이 존재한다면, 해당 방의 사용 가능한 시간을 손님의 대실 종료 시간 + 10분 후 시간으로 수정 한다.
   2. 손님의 대실 시작 시간에 사용 가능한 방이 존재하지 않는다면 손님의 대실 종료 시간 + 10분 후에 사용 가능한 새로운 방을 추가한다.
4. 모든 예약을 확인 하고 나서 존재하는 방의 개수를 반환한다.

 

소스 코드

import java.util.*;

class Solution {
    public int solution(String[][] book_time) {
    
        LinkedList<Customer> customer = new LinkedList<>();
        PriorityQueue<Room> roomList = new PriorityQueue<>();
        roomList.add(new Room(new Time("00:00")));
        for(int i = 0; i<book_time.length; i++){
            customer.add(new Customer(book_time[i][0],book_time[i][1]));
        }
        Collections.sort(customer);
        
        for(int i = 0; i<customer.size(); i++){
            PriorityQueue<Room> newRoomList = new PriorityQueue<>();
            
            boolean isCheckin = false;
            Customer curPerson = customer.get(i);
            
            while(!roomList.isEmpty()){
                Room curRoom = roomList.poll();
                if(curRoom.start.compareTo(curPerson.start) <= 0){
                    isCheckin = true;
                    curRoom.start = curPerson.end;
                    curRoom.start.add(10);
                    newRoomList.add(curRoom);
                    break;
                }
                newRoomList.add(curRoom);
            }
            while(!roomList.isEmpty()){
                Room curRoom = roomList.poll();
                newRoomList.add(curRoom);
            }
            
            if(!isCheckin){
                Room newRoom = new Room(curPerson.end);
                newRoom.start.add(10);
                newRoomList.add(newRoom);
            }            
            roomList = newRoomList;
        }
        
        return roomList.size();
    }
}

class Time implements Comparable<Time>{
    int h;
    int m;
    
    public Time(String timeString){
        String[] time = timeString.split(":");
        this.h = Integer.parseInt(time[0]);
        this.m = Integer.parseInt(time[1]);
    }
    
    public int compareTo(Time t){
        if(this.h == t.h)
            return this.m - t.m;
        else
            return this.h - t.h;
    }
    
    public void add(int m){
        this.m += m;
        if(this.m >= 60){
            this.h++;
            this.m -= 60;
        }
    }
    
    public String toString(){
        return Integer.toString(this.h) + ":" + Integer.toString(this.m);
    }
}
class Customer implements Comparable<Customer>{
    Time start;
    Time end;
    
    public Customer(String startString, String endString){
        this.start = new Time(startString);
        this.end = new Time(endString);
    }
    
    public int compareTo(Customer c){
        return this.start.compareTo(c.start);
    }
}

class Room implements Comparable<Room>{
    Time start;
     public Room(Time t){
         this.start = t;
     }
    
    public int compareTo(Room r){
        return this.start.compareTo(r.start);
    }
}