호텔 대실(프로그래머스-연습문제)

문제

코드

class Solution {
    static int count=0;
    public int solution(String[][] book_time) {
        int answer = 0;
        boolean[] check=new boolean[book_time.length];
        
        while(count!=book_time.length){
            answer++;
            String findNext="00:00";
            while(findNext!="0")
                findNext=findBook(findNext,book_time,check);      
        }
        return answer;
    }
    static public String findBook(String findNext,String[][] book_time,boolean[] check){
        int[] select={24,60};
        int afterHour=Integer.parseInt(findNext.split(":")[0]);
        int afterMinute=Integer.parseInt(findNext.split(":")[1]);
        int findIndex=-1;
        for(int i=0;i<book_time.length;i++){
            int hour=Integer.parseInt(book_time[i][0].split(":")[0]);
            int minute=Integer.parseInt(book_time[i][0].split(":")[1]);
            if(!check[i]&&hour<select[0]&&hour>=afterHour){
                if(hour==afterHour){
                    if(minute<afterMinute) continue;
                }
                select[0]=hour;
                select[1]=minute;
                findIndex=i;
            }
            else if(!check[i]&&hour==select[0]&&hour>=afterHour){
                if(hour==afterHour){
                    if(minute<afterMinute) continue;
                }
                if(minute<select[1]){
                    select[1]=minute;
                    findIndex=i;
                }
            }
        }
        if(findIndex==-1) return "0";
        else{
            count++;
            check[findIndex]=true;
            int findNextHour=Integer.parseInt(book_time[findIndex][1].split(":")[0]);
            int findNextMinute=Integer.parseInt(book_time[findIndex][1].split(":")[1]);
            if(findNextMinute+10>=60){
                findNextHour+=1;
                findNextMinute-=50;
            }
            else findNextMinute+=10;
            return findNextHour+":"+findNextMinute;
        }
    }
}

풀이

(1) 방 하나에 들어갈 예약들을 찾을 반복문을 실행한다. 그 방에 더이상 들어갈 수 있는 예약이 없으면 다음 방에서 다시 시작한다.
(2) findBook()함수는 다음 예약을 찾는 함수이다. 다음 예약을 찾는 방법은 아래와 같다.

• 아직 방이 할당되지 않은 예약이어야 하고, 현재 방의 마지막 예약의 종료시간+10분 보다 시작시간이 늦어야 한다.(방의 첫 예약을 넣을 때는 초기 시간을 00:00으로 설정한다.)
• 위와 같은 방법으로 예약들의 조건을 확인하며, 조건을 만족하는 예약 중 가장 시작시간이 이른 예약을 방에 할당한다.
• return 값으로는 할당된 예약의 종료시간 +10분을 return 한다. 만약 할당할 예약을 찾지 못했다면, "0"을 return하고, solution 함수에서는 "0"이 들어오면 다음 방부터 다시 시작한다.
• 위 과정은 모든 예약이 할당되었을 때 종료된다.

결과

크게 어렵지 않은 문제였다. 필요한 알고리즘도 딱히 없었고, 구현하는 과정이 살짝 귀찮은 문제였다. 주의할 점은 청소시간 10분을 추가하는데, 예를들어 13:55분에 종료되면 청소가 끝나면 14:05부터 다음 예약을 받을 수 있다. 그렇기 때문에 시간과 분을 주의해서 다루어주어야 한다.
살짝 코드가 길지만, 나는 그냥 의식의 흐름대로 코드를 썼다.
방에 넣을 수 있는 예약 중 가장 이른시간에 시작하는 예약을 계속 넣고, 더이상 넣을 수 없으면 다음 방으로 넘어간다. 이것도 greedy한 방법이라고 하면 그럴 수 있겠다.
최근 풀었던 문제 중 그나마 무난했던 것 같다.
출처 : 프로그래머스 코딩 테스트 연습 https://school.programmers.co.kr/learn/challenges