[Java] 호텔 대실 - Lv2 프로그래머스

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

프로그래머스

 

 

풀이

---

첫 접근부터 단순하게 생각하여

분 단위를 index로 하는 배열을 선언해서 객실 이용중일 때와 닫혔을 때를 단순 때려박아서 구하려고 했다.

 

청소를 10분간 진행하기로 했으니 분단위의 00:00~23:59인 0~1440에 청소시간을 더한 1450을 length로 두었다.

int[] fulltime = new int[24*60+10];

 

퇴실 기간이 23:51이상인 값을 고려하지 않았다. 예약 시각이 자정을 넘어가지 않는다고 하였기 때문이다.

 

각 손님들의 입실 퇴실 시간을 담을 이차원 배열을 생성하여 int형태로 저장하였다.

    (...생략...)
    int[][] time = new int[book_time.length][2];
    int idx = 0;
    for(String[] book : book_time) {
        time[idx][0] = time(book[0]);
        time[idx][1] = time(book[1]) + 9;
        idx++;
    }
}

public int time(String book) {
    int hour = Integer.parseInt(book.split(":")[0]) * 60;
    int min = Integer.parseInt(book.split(":")[1]);

    return hour + min;
}

 

이제 배열에 입력하고 조건에 따라 결과만 출력하면 되는데

for(int[] t : time){
	for(int i=t[0]; i<fulltime.length; i++{
    	if(i < t[1]{
        	fulltime[i]++;
        }
        else fulltime[i]--;
    }
    
}

처음에는 위의 코드와 같이 반복문을 쭉 돌리려고 했으나

book_time배열의 길이도 1~1000이고, t[0] ~ t[1]의 idx값이 백단위를 넘어가다보니

시간복잡도가 엄청 커질 것 같았다. 정확히 시간복잡도를 이해하지는 못하지만

time배열 길이 x time배열 안의 t[0] ~ fulltime만큼의 횟수에다가

조건문을 사용하기 때문에 또 시간이 더 소요될 거라 생각했다. 엄청 비효율적이다.

 

 

 

그리하여 아래 코드처럼 방법을 생각하게됐는데

for(int[] t : time) {
    fulltime[t[0]]++;
    fulltime[t[1]]--;
}

for(int i=1; i<fulltime.length; i++) {
    fulltime[i] += fulltime[i-1];
}

우선 대실 시작시간과 청소가완료된 시간만 체크를 한 뒤 배열을 돌며 입력시키면 배열이 아래 그림과 같이 된다.

 

 

이를 누적합 알고리즘이라고 한다고 하는데, 써먹었기 때문에 따로 포스팅을 해서 링크를 걸어두도록 하겠다.

 

여튼 이렇게 배열을 한번에 셋팅하면 딱 fulltime배열의 길이만큼만 반복을 한번 돌면 된다.

돌고나서 배열안의 가장 큰 값이 방이 소모된 갯수일 것이다.

또 반복문을 돌아 체크하지 않도록 fulltime배열안에 값을 집어넣는 과정에서 Math의 max메서드를 활용해 answer값을 셋팅할 수 있게 했다.

 

문제 예시에서 주어진 그림설명도 아래와 같이 될 것이다.

 

 

 

전체코드

---

class Solution {
    public int solution(String[][] book_time) {
    	int answer = 0;
    	int[] fulltime = new int[24*60+10];
    	int[][] time = new int[book_time.length][2];
    	int idx = 0;
        for(String[] book : book_time) {
        	time[idx][0] = time(book[0]);
        	time[idx][1] = time(book[1]) + 10;
            idx++;
        }
        
        for(int[] t : time) {
        	fulltime[t[0]]++;
        	fulltime[t[1]]--;
        }
        
        for(int i=1; i<fulltime.length; i++) {
        	fulltime[i] += fulltime[i-1];
        	answer = Math.max(answer, fulltime[i]);
        }
        
        return answer;
    }
    
    public int time(String book) {
    	int hour = Integer.parseInt(book.split(":")[0]) * 60;
    	int min = Integer.parseInt(book.split(":")[1]);
    	
    	return hour + min;
    }
}

 

 

 

참조

누적합 알고리즘

https://nahwasa.com/entry/%EB%88%84%EC%A0%81-%ED%95%A9prefix-sum-2%EC%B0%A8%EC%9B%90-%EB%88%84%EC%A0%81%ED%95%A9prefix-sum-of-matrix-with-java

누적 합(prefix sum), 2차원 누적합(prefix sum of matrix) with java