호텔 대실

문제 설명

호텔을 대실하는데, 방의 시간이 겹치지 않게 해서 대실할 수 있는 방의 수를 구하는 문제이다.

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

프로그래머스

문제 풀이

첫 번째 접근

일단 문제가 시간으로 이루어져 있으니 모두 분으로 고쳐야겠다고 생각했다.

그리고 시작 시간을 기준으로 배열을 정렬한 후 최약의 경우 book_time의 길이가 1,000이므로 2차 반복문을 돌려도 충분하겠다고 판단했다.

 

1. '시간*60 + 분'으로 시간을 계산해준다.

    for book in book_time:
        start = book[0].split(":")
        end = book[1].split(":")
        newTime.append([makeTime(int(start[0]), int(start[1])), makeTime(int(end[0]), int(end[1]))])

2. 새로 만든 시간 배열을 정렬한다.

newTime.sort(key=lambda x: (x[0], x[1]))

3. 만일 현재를 시간을 기준으로 해당 방에 다른 시간을 배정할 수 있으면 그 방을 True로 둔다. 참고로 청소 시간이 10분 있으므로 끝나는 시간에 10을 더해줘야 한다.

    for i in range(len(newTime)-1):
        if not visit[i]:
            answer += 1
            visit[i] = True
            startC = newTime[i][0]
            endC = newTime[i][1] + 10
            for j in range(i, len(newTime)):
                startN = newTime[j][0]
                endN = newTime[j][1] + 10
                if not visit[j]:
                    if endC <= startN:
                        visit[j] = True
                        endC = endN

4. 맨 마지막 타임에 추가적인 방을 할당해야 할 경우 맨 마지막 시간은 방문되지 않았으므로 방문했는지 확인 후 answer에 1을 더해준다.

    if not visit[len(visit)-1]:
        answer += 1

코드

python

def makeTime(hour, minute):
    answerTime = hour*60 + minute
    
    return answerTime
    

def solution(book_time):
    answer = 0
    newTime = []
    visit = [False for _ in range(len(book_time))]
    
    for book in book_time:
        start = book[0].split(":")
        end = book[1].split(":")
        newTime.append([makeTime(int(start[0]), int(start[1])), makeTime(int(end[0]), int(end[1]))])
    
    newTime.sort(key=lambda x: (x[0], x[1]))
    
    for i in range(len(newTime)-1):
        if not visit[i]:
            answer += 1
            visit[i] = True
            startC = newTime[i][0]
            endC = newTime[i][1] + 10
            for j in range(i, len(newTime)):
                startN = newTime[j][0]
                endN = newTime[j][1] + 10
                if not visit[j]:
                    if endC <= startN:
                        visit[j] = True
                        endC = endN
    
    if not visit[len(visit)-1]:
        answer += 1

    return answer

java

import java.util.*;

class Solution {
    
    public int makeTime(int hour, int min){
        return hour*60 + min;
    }
    
    public int solution(String[][] book_time) {
        int answer = 0;
        int length = book_time.length;
        int[][] newTime = new int[length][2];
        boolean[] visit = new boolean[length];
        
        for(int i = 0; i<length; i++){
            for(int j=0; j<2; j++){
                StringTokenizer st = new StringTokenizer(book_time[i][j], ":");
                int hour = Integer.parseInt(st.nextToken());
                int min = Integer.parseInt(st.nextToken());
                newTime[i][j] = makeTime(hour, min);
            }
        }
        
        
        Arrays.sort(newTime, (o1, o2) ->{
            if(o1[0] == o2[0]){
                return o1[1] - o2[1];
            }else{
                return o1[0]-o2[0];
            }
        });
        
        for(int i=0; i<length-1; i++){
            if(visit[i] == false){
                int startC = newTime[i][0];
                int endC = newTime[i][1] + 10;
                visit[i] = true;
                answer += 1;
                for(int j=i+1; j<length; j++){
                    int startN = newTime[j][0];
                    int endN = newTime[j][1] + 10;
                    if(visit[j] == false){
                        if(endC <= startN){
                            endC = endN;
                            visit[j] = true;
                        }
                    }
                }
            }
        }
        
        if(visit[length-1] == false){
            answer += 1;
        }
        
        return answer;
    }
    
}