[프로그래머스] Lv.2 호텔 대실 (JAVA)

프로그래머스

이 문제는 보자마자 아래처럼 풀어야겠다는 생각이 들었다. 그래야 공백 없이 확실하게 들어갈 수 있기 때문.

우선순위 큐로 풀어도 될 것 같은데 dfs로 풀고싶어서 dfs로 풀었다.. 근데 pq로 푸는게 더 효율적인 코드일듯.

 

문제풀이

1. 우선 종료시간에 +10분을 추가해준다(청소시간)

// 대실 종료 시간에 + 10분
// 단, 23:59에는 더이상 손님이 들어오지 않으니 + 10분 하지 않음.
static String[][] timeFix(String[][] time, int cleanTime){
    for(int i=0; i<N; i++){
       String[] tmp = time[i][1].split(":");
        int hour = Integer.parseInt(tmp[0]);
        int minute = Integer.parseInt(tmp[1])+cleanTime;
        if(minute >= 60) {
            hour++; minute -= 60;
        }
        if(hour >= 24) {
            hour = 23; minute = 59;
        }
        String hours = hour+"";
        String minutes = minute+"";
        if(hour < 10){
            hours = "0"+hour;
        }
        if(minute < 10){
            minutes = "0"+minute;
        }
        time[i][1] = hours+":"+minutes;
    }
    return time; 
}

int로 바꿔서 풀까 하다가 그냥 compareTo 사용하려고 String으로 풀었다.

 

2. book_time 배열을 시작시간 기준으로 정렬 (0: 시작시간, 1: 종료시간)

// book_time을 오름차순으로 정렬
Arrays.sort(book_time, new Comparator<String[]>(){
    public int compare(String[] o1, String[] o2) {
        if(o1[0].equals(o2[0])){
            return o1[1].compareTo(o2[1]);
        }else{
            return o1[0].compareTo(o2[0]);   
        }
    }
});

2차원배열이기 때문에 Comparator 사용해서 정렬해줬다.

 

3. dfs를 돌면서 처음 방문한 시각이면서 && 현재 종료시간 <= 다음 시작시간인 시간을 찾는다

// dfs 돌면서 다음에 넣을 수 있는 방을 찾아서 넣어준다.
static void dfs(int idx, String[][] time){
    for(int i=0; i<N; i++){
        if(!visited[i] && time[idx][1].compareTo(time[i][0]) <= 0){
            visited[i] = true;
            dfs(i, time);
            break;
        }
    }
}

여기서 문제가 있었는데, dfs(i, time); 뒤에 break;를 걸어줘야한다.

[["09:00", "09:10"], 
 ["09:10", "09:20"], 
 ["09:20", "09:30"], 
 ["09:30", "09:40"], 
 ["09:40", "09:50"], 
 ["09:50", "10:00"]]

이 예시를 들어 설명해보자면, 처음 dfs에 ["09:00", "09:10"]이 들어간다.

이후에 당연히 ["09:20", "09:30"]으로 이동하고 ["09:40", "09:50"]으로 간 다음 멈춘다고 생각하겠지만

여기서 break;를 걸어주지 않는다면 맨 처음에 들어온 값인 09:10을 기준으로 방문할 수 있는 모든 경우를 방문하게 된다.

[true, false, true, true, true, true]

dfs가2번 손님 빼고 모두를 1번 방에 들여보내는 문제가 발생한다.

 

전체코드

import java.io.*;
import java.util.*;

class Solution {
    static boolean visited[];
    static int N;
    public int solution(String[][] book_time) {
        int answer = 0;
        N = book_time.length;
        
        visited = new boolean[N];
        
        // 종료 시간에 10분씩 더하기
        book_time = timeFix(book_time, 10);
        
        // book_time을 오름차순으로 정렬
        Arrays.sort(book_time, new Comparator<String[]>(){
           public int compare(String[] o1, String[] o2) {
               if(o1[0].equals(o2[0])){
                    return o1[1].compareTo(o2[1]);
               }else{
                    return o1[0].compareTo(o2[0]);   
               }
           }
        });
        
        for(int i=0; i<N; i++){
            if(!visited[i]){
                visited[i] = true;
                dfs(i, book_time);
                answer++;
            }else{
                continue;
            }
        }
        return answer;
    }
    
    // dfs 돌면서 다음에 넣을 수 있는 방을 찾아서 넣어준다.
    static void dfs(int idx, String[][] time){
        for(int i=0; i<N; i++){
            if(!visited[i] && time[idx][1].compareTo(time[i][0]) <= 0){
                visited[i] = true;
                dfs(i, time);
                break;
            }
        }
    }
    
    // 대실 종료 시간에 + 10분
    // 단, 23:59에는 더이상 손님이 들어오지 않으니 + 10분 하지 않음.
    static String[][] timeFix(String[][] time, int cleanTime){
        for(int i=0; i<N; i++){
            String[] tmp = time[i][1].split(":");
            int hour = Integer.parseInt(tmp[0]);
            int minute = Integer.parseInt(tmp[1])+cleanTime;
            if(minute >= 60) {
                hour++; minute -= 60;
            }
            if(hour >= 24) {
                hour = 23; minute = 59;
            }
            String hours = hour+"";
            String minutes = minute+"";
            if(hour < 10){
                hours = "0"+hour;
            }
            if(minute < 10){
                minutes = "0"+minute;
            }
            time[i][1] = hours+":"+minutes;
        }
        return time; 
    }
}