2021 - 광고 삽입

https://programmers.co.kr/learn/courses/30/lessons/72414#fnref1

코딩테스트 연습 - 광고 삽입

[ 문제풀이 ]

카카오는 시간을 초로 변환하여 처리하는 문제가 자주 출제되는 것 같다. 이 문제 역시 마찬가지로 시간을 초로 변환하여 각 시간마다 누적 시청자 수를 구해주면 해결할 수 있는 문제이다.

​누적 시청자 수를 구할 때 매번 처음부터 구해줄 필요가 없이 이전 값과 다음 값만 연산해주면 된다.

​누적 시청자 수가 int 범위를 넘어갈 수 있기 때문에 long으로 선언해주자.

class Solution {
    public String solution(String play_time, String adv_time, String[] logs) {
        int playTime = stringToInt(play_time);
        int[] time = new int[playTime];
        
        for (String log : logs) {
            String[] t = log.split("-");
            int startTime = stringToInt(t[0]);
            int endTime = stringToInt(t[1]);
            
            //(startTime ~ endTime - 1)까지 누적 시청자 수 증가
            for (int i = startTime; i < endTime; ++i) {
                time[i]++;
            }
        }
        
        int advTime = stringToInt(adv_time);
        
        int insertTime = 0;
        long max = 0;
        for (int i = 0; i < advTime; ++i) {
            max += time[i];
        }
        
        long sum = max;
        //제일 앞 시청자 수를 빼고 현재 마지막 다음 시청자 수를 더해주면서 insertTime 갱신
        for (int i = advTime; i < playTime; ++i) {
            sum -= time[i - advTime];
            sum += time[i];
            
            if (max < sum) {
                max = sum;
                insertTime = i - advTime + 1;
            }
        }
        
        return intToString(insertTime);
    }
    
    //문자열 시간을 정수형 시간으로 변환
    public int stringToInt(String time) {
        String[] t = time.split(":");
        return Integer.parseInt(t[0]) * 3600 + Integer.parseInt(t[1]) * 60 + Integer.parseInt(t[2]);
    }
    
    //정수형 시간을 문자열 시간으로 변환
    public String intToString(int time) {
        int hour = time / 3600;
        time %= 3600;
        int minute = time / 60;
        time %= 60;
        
        return String.format("%02d:%02d:%02d", hour, minute, time);
    }
}

---

이후에 찾아보니 위의 방법은 최악의 경우에는 시간 초과가 발생한다.

​왜냐하면 모든 log에 대해서 O(N)의 연산으로 시간을 누적시키는 방법은 최악의 경우 300000(log의 개수) x 360000(최대 시간, 00:00:01 ~ 99:59:59) 만큼의 시간이 걸리기 때문이다.

​이를 해결하기 위해서는 먼저 모든 log에 대해서 시작 부분과 종료 부분을 +1, -1로 누적시켜준다. 이때 +1, -1은 현재 시간에 누적된 시청자 수는 이전 시간의 누적된 시청자 수 보다 1만큼 증가/감소하였다는 의미이다.

​예를 들어 1~6, 4~8의 log가 있다고 하자. 누적된 time 배열은 다음과 같다.

time   : 0 0 1 1 0 -1 0 -1
second : 1 2 3 4 5  6 7  8

3, 4초에 각각 1명의 시청자가 새롭게 시청하였음을 뜻한다. 반대로 6, 8초에는 각각 1명의 시청자가 종료하였음을 뜻한다.

​모든 log에 대해서 시작 부분과 종료 부분을 누적하였다면 처음부터 마지막까지 가면서 시간을 누적해주면 된다.

​왜냐하면 time 배열의 값은 시작 부분이거나 종료 부분의 시청자가 누적된 것이기 때문에 time[i]의 값은 time[i - 1]의 시청자 수에서 시작/종료한 시청자 수를 뜻하기 때문이다.

time   : 0 0 1 2 2 1 1 0
second : 1 2 3 4 5 6 7 8

위의 값은 모든 log에 대해서 O(N)의 시간으로 모든 시간을 누적한 결괏값과 동일하다. 이 방법을 이용하면 훨씬 빠른 시간으로 누적 시간을 구할 수 있다.

class Solution {
    public String solution(String play_time, String adv_time, String[] logs) {
        int playTime = stringToInt(play_time);
        int[] time = new int[360001];
        
        for (String log : logs) {
            String[] t = log.split("-");
            int startTime = stringToInt(t[0]);
            int endTime = stringToInt(t[1]);
            
            //시작 시간과 종료 시간만 누적
            time[startTime]++;
            time[endTime]--;
        }
        
        //이전 값에 대해 계속 누적
        for (int i = 1; i < playTime; ++i) {
            time[i] += time[i - 1];
        }
        
        int advTime = stringToInt(adv_time);
        
        int insertTime = 0;
        long max = 0;
        for (int i = 0; i < advTime; ++i) {
            max += time[i];
        }
        
        long sum = max;
        //제일 앞 시청자 수를 빼고 현재 마지막 다음 시청자 수를 더해주면서 insertTime 갱신
        for (int i = advTime; i < playTime; ++i) {
            sum -= time[i - advTime];
            sum += time[i];
            
            if (max < sum) {
                max = sum;
                insertTime = i - advTime + 1;
            }
        }
        
        return intToString(insertTime);
    }
    
    //문자열 시간을 정수형 시간으로 변환
    public int stringToInt(String time) {
        String[] t = time.split(":");
        return Integer.parseInt(t[0]) * 3600 + Integer.parseInt(t[1]) * 60 + Integer.parseInt(t[2]);
    }
    
    //정수형 시간을 문자열 시간으로 변환
    public String intToString(int time) {
        int hour = time / 3600;
        time %= 3600;
        int minute = time / 60;
        time %= 60;
        
        return String.format("%02d:%02d:%02d", hour, minute, time);
    }
}