프로그래머스_호텔 대실_Day8

알고리즘 챌린지 8일 차이다. 막상 시작해 보니 어찌어찌하고 있기는 한데, 조금 더 열심히 하려면 주말은 쉬는 걸로 할 걸 그랬나 보다.. 다다음주에는 여행을 가니 할 수 있을 때 열심히 꾸준히 해야겠다. 

오늘도 프로그래머스 Level2에 분류된 문제를 가지고 왔다. 

https://school.programmers.co.kr/learn/courses/30/lessons/155651?language=java

프로그래머스

다양한 방법으로 풀 수 있겠지만 필자는 비교적 간단하게 구간합 알고리즘을 사용했다. 
배열의 길이가 1000개이므로 완전 탐색을 사용해도 될 것 같지만,,, 가능하다면 시간복잡도를 줄여서 푸는 게 효율적이기 때문에 습관을 들여놓고자 한다. 

1차원 배열에서 구간합을 구하는 로직은 단순하다. 구간의 시작값에는 +1, 구간의 끝 값+1에는 -1을 해둔다음, 이전 인덱스의 값을 현재 인덱스의 값에 누적합을 구하는 방식이다. 아래 그림을 참고하기 바란다.

1. 호텔 이용 시간의 최소 단위가 분이기 때문에 단위를 분으로 일원화 한 후에 1차원 배열의 크기를 1450(24 * 60 + 10)으로 만든다. 
2. 주어진 book_time 배열을 순회하면서 시작 시각과 끝 시각의 각각 1, -1을 초기화해준다. 
3. index를 1부터 시작해서 배열의 끝까지 순회하며 누적합을 구한다. 
4. 누적합의 최대 값이 동시간대 겹치는 방의 수 즉, 필요한 최소 객실 수가 된다. 

 

이 때, 한 가지 유의해야 할 점이 있는데, 입출력 예 #2의 경우이다. 

직관적으로 봤을 때, 앞 타임 사용자가 퇴실 후에 10분 청소를 하고 뒤 타임 사용자를 받을 수 있을 것 같아서 간단하게 넘어갈 수 있을 것이다. 하지만 위의 구간합 개념을 적용하다 보면, 끝 시각 + 10에서 겹침이 발생하여 객실수가 잘못 나오게 된다. 
즉, 10시 10분에 퇴실 후 10시 19분까지는 사용 불가, 10시 20분부터는 사용이 가능한 상태로 있어야 하기 때문에, 기존의 구간합 과는 다르게 끝 값+1이 아니라 끝 값에 -1을 해주어야 한다. 

아래 코드로 살펴보자.

Java

class Solution {
    private final int MAX_TIME = 1450;
    private final int CLEAN_TIME = 10;
    private final int HOUR = 60;
    public int solution(String[][] book_time) {
        int answer = 0;
        
        int [] room = new int[MAX_TIME];
        for(String [] book : book_time) {
            String inTime = book[0];
            String outTime = book[1];
            
            room[calling(inTime)] += 1;
            room[calling(outTime) + CLEAN_TIME] -= 1;
        }
        
        for(int i=1; i<MAX_TIME; i++) {
            room[i] += room[i-1];
            answer = answer < room[i] ? room[i] : answer;
        }
        
        return answer;
    }
    public int calling(String time) {
        String hour = time.split(":")[0];
        String minute = time.split(":")[1];
        
        return Integer.parseInt(hour) * HOUR + Integer.parseInt(minute);
    }
}

Python

MAX_TIME = 1450
HOUR = 60
CLEAN_TIME = 10

def solution(book_time):
    answer = 0
    room = [0] * 1450
    for b in book_time:
        inTime = b[0]
        outTime = b[1]
        
        room[calling(inTime)] += 1
        
        room[calling(outTime) + CLEAN_TIME] += -1
    
    for i in range(1, len(room)):
        room[i] += room[i-1]
        answer = max(answer, room[i])
        
    return answer

def calling(time):
    time_list = time.split(":")
    hour = time_list[0]
    minute = time_list[1]

    return int(hour) * HOUR + int(minute)