프로그래머스) 호텔 대실

사용 언어: java11

 

 

 

문제를 풀고 나서 다른 분들의 풀이를 살펴보니 조금 더 간결한 코드로 정답을 맞추게 되어 공유하게 됐습니다.

테스트 통과 시간을 비교했을 때 1-2 밀리초 더 빠른 시간을 보였습니다.

그럼 거두절미하고 바로 문제 풀이 방법에 대해 설명드리도록 하겠습니다.

 

 

 

접근 방법

 

출처: 프로그래머스 - 호텔 대실에 대한 입출력 예 #1

 

 

위의 예제를 참고하니 시간이 겹치는 부분마다 무조건 방을 늘릴 수 밖에 없었습니다.

그래서 시간테이블 배열(timeTable)을 하나 만들어 예약 시간부터 청소 시간을 포함한 퇴실 시간까지 1씩 더하는 방법을 떠올렸습니다.

먼저 book_time의 길이만큼 timeTable에서 예약 시간과 청소를 포함한 퇴실 시간까지의 범위를 고려해야 합니다.

 

- 시각의 범위는 00:00 ~ 23:59인데 시 + 분으로 배열의 크기를 정한다면 23 * 60 + 60 + 10 (10은 청소 시간) 이고 계산하면 총 크기는 1450입니다.

- book_time의 길이는 최대 1000입니다.

- 결국 1000 * 1450 = 1450000 으로 충분히 1초 내에 풀 수 있음을 알 수 있습니다.

 

 

이제 배열의 크기까지 알았으니 배열을 초기화하고 시각 범위 내의 index 위치에 1씩 추가합니다.

private static final short MAX = 23 * 60 + 60 + 10;

    public int solution(String[][] book_time) {
        int[] timeTable = new int[MAX];
        for (String[] strings : book_time) {
            int start = getMinutes(strings[0]);
            int end = getMinutes(strings[1]) + 10;

            for (int i = start; i < end; i++) {
                timeTable[i]++;
            }
        }
   	...

주의할 점은 청소가 끝난 시점에 다음 손님을 받을 수 있기 때문에 i의 범위를 end 미만까지 반복문을 돌렸습니다.

 

 

 

이후에 가장 시간이 겹치는 구간(최댓값)을 찾아 정답을 반환합니다.

int answer = 0;
for (int i = 0; i < MAX; i++) {
	answer = Math.max(answer, timeTable[i]);
}
return answer;

 

 

 

시간 복잡도

 

N = book_time의 길이이고, M = 시각의 범위라고 한다면 O(N * M) + O(M) 이고

총 O(N * M)의 시간복잡도를 가집니다.

 

 

 

코드

 

class Solution {

    private static final short MAX = 23 * 60 + 60 + 10;

    public int solution(String[][] book_time) {
        int[] timeTable = new int[MAX];
        for (String[] strings : book_time) {
            int start = getMinutes(strings[0]);
            int end = getMinutes(strings[1]) + 10;

            for (int i = start; i < end; i++) {
                timeTable[i]++;
            }
        }
        int answer = 0;
        for (int i = 0; i < MAX; i++) {
            answer = Math.max(answer, timeTable[i]);
        }
        return answer;
    }

    private int getMinutes(String s) {
        String[] time = s.split(":");
        int hour = Integer.parseInt(time[0]);
        int minute = Integer.parseInt(time[1]);
        return hour * 60 + minute;
    }
}

 

 

채점한 결과