[Programmers] 광고 삽입

누적합과 슬라이딩 윈도우를 이용하는 문제였다.

우선적으로 모든 시청자들의 시간을 배열에 누적해주었다. 그 다음 접근법을 고민해보았다. 이 문제 같은 경우 광고시간이 크기 N으로 고정이기 때문에 이것을 전체 배열길이에서 만큼 한칸씩 밀면서 움직여보며 답을 찾는 방법인 슬라이딩 윈도우를 적용시켜보았다.  

기본적으로 아이디어는 맞았지만 문제를 풀면서 주의할점이 여러가지 있었다.
첫째, 시간을 초로 바꿔서 푸는 부분
둘째, 동영상 재생시간 = 재생 종료된 시간 - 재생 시작된 시간 이므로 재생종료시간을 포함 X
셋째, 슬라이딩 윈도우 크기 만큼의 배열 합 값이 int 범위를 넘어갈 수 있는 부분
위의 부분을 고려하여 반례들을 해결할 수 있었다.

package algostudy2;
 
import java.util.StringTokenizer;
 
public class Solution_2021카카오_광고삽입 {
    public static void main(String[] args) {
        String play_time = "02:03:55";
        String adv_time = "00:14:15";
        String[] logs = {"01:20:15-01:45:14", "00:40:31-01:00:00", "00:25:50-00:48:29", "01:30:59-01:53:29", "01:37:44-02:02:30"};
 
        // String play_time = "99:59:59";
        // String adv_time = "25:00:00";
        // String[] logs = {"69:59:59-89:59:59", "01:00:00-21:00:00", "79:59:59-99:59:59", "11:00:00-31:00:00"};
 
        // String play_time = "50:00:00";
        // String adv_time = "50:00:00";
        // String[] logs = {"15:36:51-38:21:49", "10:14:18-15:36:51", "38:21:49-42:51:45"};
 
        System.out.println(solution(play_time, adv_time, logs));
    }
 
    static String solution(String play_time, String adv_time, String[] logs) {
        int totalPlaySeconds = toSeconds(play_time);
        int advSeconds = toSeconds(adv_time);
 
        int[] sumOfLog = new int[totalPlaySeconds + 1];
 
        for (String log : logs) {
            StringTokenizer st = new StringTokenizer(log, "-");
 
            int start = toSeconds(st.nextToken());
            int end = toSeconds(st.nextToken());
 
            for (int i = start; i < end; i++) {
                sumOfLog[i]++;
            }
        }
 
        //window init
        int startOfAdv = 0;
        int endOfAdv = advSeconds;
 
        long sum = 0;
        for (int i = startOfAdv; i < advSeconds; i++) {
            sum += sumOfLog[i];
        }
 
        long answerOfSum = sum;
        int answerOfStart = startOfAdv;
 
        while (true) {
            if (endOfAdv == totalPlaySeconds + 1) {
                break;
            }
 
            sum = sum - sumOfLog[startOfAdv++] + sumOfLog[endOfAdv++];
 
            if (sum > answerOfSum) {
                // System.out.println(sum + ", " + toTime(startOfAdv) + ", " + toTime(endOfAdv));
                answerOfSum = sum;
                answerOfStart = startOfAdv;
            }
        }
 
        return toTime(answerOfStart);
    }
 
    static int toSeconds(String str) {
        int seconds = 0;
        StringTokenizer st = new StringTokenizer(str, ":");
 
        seconds += 3600 * Integer.parseInt(st.nextToken());
        seconds += 60 * Integer.parseInt(st.nextToken());
        seconds += Integer.parseInt(st.nextToken());
 
        return seconds;
    }
 
    static String toTime(int time) {
        int hour = time / 3600;
        time = time - (hour * 3600);
 
        int minute = time / 60;
        time = time - (minute * 60);
 
        int second = time;
 
        return (hour < 10 ? "0" + hour : hour) + ":" +
            (minute < 10 ? "0" + minute : minute) + ":" +
            (second < 10 ? "0" + second : second);
    }
}