[프로그래머스,Java] Level2: 호텔 대실

 

문제분석:

 

전형적인 스케쥴링 문제이다.

 

제일 쉽게 푸는방법은

 

0시부터 24시까지  1분마다 체크하여 입실,퇴실조치를 하면 편하다.

 

근데, 이 방법은 효율성이 매우 나쁜건 누구나 아는사실이고 

실제로 이방법보다 효율성 좋게 스케쥴링하는방법이 널렸다.

 

근데 이 문제는 앞선 방법으로해도 풀린다...

 

그래도 귀찮터라도 효율적인방법으로 접근했다.

 

 

전략: 실제로 인간이 스케쥴링했을때 시뮬레이션대로 코드작성

 

말 그대로, 인간이 스케쥴했을때를 가정하여 짠다.

 

1. 우선 입실시간순 대로 정렬한뒤, 입실처리를한다.

 

2. 만약 퇴실시간이 되면 퇴실한다

But, 우리는 1분마다 체크를하는 방법은 포기했으니 다른 방법으로 퇴실시간을 체크한다.

 

Arrange 2 : 이후에 입장할 사람의 입장할 시간보다 적은 퇴실시간은 퇴실조치한다. 

 

이 전략대로 풀것이다.

 

 

먼저, 퇴실대기 리스트가 필요하다.  

 

이 퇴실대기 리스트는,  손님이 입장할때, 실시간으로 퇴실시간이 빠른순대로 정렬이되어야하므로, PQ를 사용했다.

 

기존 예약리스트는, 시작시간 순대로 정렬한다.

 

TimeToInt는 문자열로 작성된 시간을 숫자로 바꾸는 간단한 메소드다.

 

time은 현재시각

count는 최소 Room을 판별하기위한 변수idx는 입장할사람의 idx다.

 

여기서 우리가 관심있는건 최소 Room의 갯수이기때문에, 반복은 입장이 모두 끝날때까지만 탐색한다. 

 

퇴실 대기리스트에 10분더 추가해서 넣는다. 청소시간이기때문이다.

 

그 후, 퇴실이 가능하면 퇴실시킨다.

 

퇴실이 몇명이 가능할지모르니 While문으로 작성했고,  퇴실이안되면 바로 break해주자.

 

-> 일련의 과정이 완료되면  최소 Room의 갯수를 갱신하자.

문제풀이

import java.util.*;
class Solution {
    public int solution(String[][] book_time) {
        int answer = 0;
        int size = book_time.length;
        PriorityQueue<Integer> end = new PriorityQueue<>();
 
        Arrays.sort(book_time,(a,b)->(TimeToInt(a[0])-TimeToInt(b[0])));
 
        int idx=0;
        int time=0;
        int count=0;
 
        while(idx!=size){
 
            end.add(TimeToInt(book_time[idx][1])+10);
            time=TimeToInt(book_time[idx][0]);
            count++;
            idx++;
            
            //퇴실이가능하면 퇴실
            while(true){
                if(time>=end.peek()){
                    end.poll();
                    count--;
                }
                else{
                    break;
                }
            }
 
            answer=Math.max(answer,count);
        }
 
        return answer;
    }
 
    public int TimeToInt (String time){
 
        String[] clock = time.split(":");
 
 
        return Integer.parseInt(clock[0])*60+Integer.parseInt(clock[1]);
 
    }
}