[Programmers | JAVA] 광고 삽입 - 슬라이딩 윈도우

우선 먼저 슬라이딩 윈도우의 알고리즘에 대해 알고 문제를 풀려고 합니다.

 

그 이유는 '광고 삽입'의 문제는 전형적인 슬라이딩 윈도우 문제라고 생각이 되기 때문입니다.

전형적인 슬라이딩 윈도우 문제란 주어진 배열에서 고정된 개수의 범위에서 최댓값을 구하는 문제! 라고 생각합니다.

 

패킷 흐름제어 알고리즘

 

위는 네트워크 통신시 패킷 흐름제어에서 사용하는 슬라이딩 윈도우 알고리즘입니다. 

 

역시 저희는 코드로 보는게 가장 빠르게 이해가 되는 부분이라고 생각합니다. 바로 보시죠.

// advLength = 14분 51초
// playLength = 1시간 20분 12초

for(int i = advLength; i<playLength; i++) {
	// 새로운 값 ad[i], 이전에 더했었던 값 ad[i-advLength]
	sum += ad[i] - ad[i-advLength];
	if(sum > max) {
		max = sum;
	}
}

/**
* 슬라이딩 윈도우 형식
* 1 2 3 4 5 6
* [1 2 3] 4 5 6
* 1 [2 3 4] 5 6
*/

 

알고보니 어렵지 않죠?

 

이런 식으로 진행하면 고정된 범위 내에서 가장 최대의 값을 구하는 유형의 문제를 풀 수 있을거에요. 다르게 풀어야하는 유형도 있을 수 있지만요.

 

각설하고 일단 해답 코드부터 보시죠.

 

class Solution {
    public String solution(String play_time, String adv_time, String[] logs) {
        int play_len = timeToInt(play_time);
        int adv_len = timeToInt(adv_time);

        long[] ad = new long[360_000];

        for(String log : logs) {
            String[] l = log.split("-");
            int start = timeToInt(l[0]);
            int end = timeToInt(l[1]);
            ad[start]++;
            ad[end]--;
        }

        // 누적 시청자 수 계산
        for(int i = 1; i < play_len; i++) {
            ad[i] += ad[i-1];
        }

        // 누적합을 다시 한 번 더 계산하여 각 시점에서의 총 시청자 수를 구함
        for(int i = 1; i < play_len; i++) {
            ad[i] += ad[i-1];
        }

        long max_sum = ad[adv_len-1];
        int max_idx = 0;

        for(int i = adv_len; i < play_len; i++) {
            if(ad[i] - ad[i-adv_len] > max_sum) {
                max_sum = ad[i] - ad[i-adv_len];
                max_idx = i - adv_len + 1;
            }
        }

        return timeToString(max_idx);
    }

    static int timeToInt(String time) {
        String[] times = time.split(":");
        int toSec = 3600;
        int totalTime = 0;
        for(String t : times) {
            int num = Integer.parseInt(t);
            totalTime += num * toSec;
            toSec /= 60;
        }
        return totalTime;
    }

    static String timeToString(int time) {
        String t = "";
        int hour = time / 3600;
        time %= 3600;
        t += String.format("%02d:", hour);

        int minute = time / 60;
        time %= 60;
        t += String.format("%02d:", minute);

        int second = time;
        t += String.format("%02d", second);

        return t;
    }
}