광고 삽입

문제 풀이

누적합을 이용해서 푸는 문제이다. 문제에서 주어진 playtime은 100시간을 넘지 않으므로 100시간을 초로 바꾸면 360000초 배열로 둘 수 있다. 배열로 두고 배열의 각 인덱스는 1초를 가리키므로 해당 구간의 재생시간을 구하면 된다.

1. 주어진 logs 배열로 totalTime을 초기화 시킨다.
   1. 시청자들의 시청 시간을 초로 바꾼다.
   2. 시작시간에는 +1을 해준다.
   3. 끝나는 시간엔 -1을 해준다.
2. totalTime[i] += totalTime[i-1]을 playtime까지 for문을 돌려준다.
   1. logs배열로 시청자들의 재생 시작 시간, 재생 끝나는 시간을 표시했으므로 totalTime[i] += totalTime[i-1]을 돌리면 해당 구간에서 재생한 시청자 수가 나온다.

         totalTime이 아래와 같이 된 경우 for문을 돌리게 되면,
         index 0 1 2 3 4 5  6  7 8 9  10
         value 0 0 1 0 1 0 -1  0 0 0  -1
      
         index 0 1 2 3 4 5  6  7 8 9  10
         value 0 0 1 1 2 2  1  1 1 1   0
         위와 같이 해당 초 구간을 재생한 시청자들을 알게 된다.
      

3. 한번 더 totalTime[i] += totalTime[i-1]을 playtime까지 for문을 돌려준다.(누적합)
   1. 광고 구간에 대한 누적 재생시간을 알기 위해서 for문을 한번 더 돌린다.
4. 구한 누적합을 바탕으로, 0playtime-adtime까지 for문을 돌리면서, iadTime+i을 광고 구간으로 두고 누적합이 가장 큰 경우를 찾으면 된다.

구한 시작 지점에 +1를 하는 이유?

    시청자들의 재생 시작 시간, 재생 끝나는 시간을 표시한 배열(logs를 for문)
    index 0 1 2 3 4 5  6  7 8 9  10
    value 0 0 1 0 1 0 -1  0 0 0  -1

    각 구간의 시청자들의 재생 횟수를 표시한 배열(totalTime[i] += totalTime[i-1]를 for문)
    index 0 1 2 3 4 5  6  7 8 9  10
    value 0 0 1 1 2 2  1  1 1 1   0

    구간까지의 누적합 배열(totalTime[i] += totalTime[i-1]를 for문)
    index 0 1 2 3 4 5  6  7 8 9  10 11
    value 0 0 1 2 4 6  7  8 9 10 10 10

    겹쳐진 재생시간보다 광고 시간이 작을때는(여기서는 4초라고 하자)
    totalTime[adTime+i] - totalTime[i]의 값을 구하는 것이니까
    1~5인 경우도 6으로 최댓값이라고 볼 수 있다. 하지만 재생 시간의 시작은 2초이므로 +1를 해줘야한다.
    그래서 생각해본 경우들은 1씩 차이가 나는 부분이 연속된다고 하면 시청자가 재생하기 전의 시간인 0을 시작지점으로 잡아서 +1을 해줘야하는 것 같다.

소스 코드

const getTime = (time) => {
    const [hour, minute, second] = time.split(":");
    return Number(hour)*3600 + Number(minute)*60 + Number(second);
}

const padZero2 = (time) => String(time).padStart(2, 0); 

const convert = (time) => {
    const hour = parseInt(time / 3600);
    const minute = parseInt((time % 3600) / 60);
    const second = time - hour*3600 - minute*60;
    return `${padZero2(hour)}:${padZero2(minute)}:${padZero2(second)}`;
}

function solution(play_time, adv_time, logs) {
    const totalTime = Array(360000).fill(0);
    const adTime = getTime(adv_time);
    const playTime = getTime(play_time);
    
    for(let i=0 ; i<logs.length ; i++){
        const [start, end] = logs[i].split("-").map(e => getTime(e));
        totalTime[start] += 1;
        totalTime[end] -= 1;
    }
    
    for(let i=1 ; i<playTime ; i++){
        totalTime[i] += totalTime[i-1];
    }
    
    for(let i=1 ; i<playTime ; i++){
        totalTime[i] += totalTime[i-1];
    }
    let max = totalTime[adTime];
    let start = 0;

    for(let i=0 ; i<playTime-adTime ; i++){
        if(totalTime[adTime+i] - totalTime[i] > max){
            max = totalTime[adTime+i] - totalTime[i];
            start = i;
        }
    }
    
    return start !== 0 ? convert(start+1) : convert(start);
}