[JS] 광고 삽입

누적합을 활용하면 해결할 수 있는 문제이다.

 

만약 10칸의 크기가 있는 배열에서 4~7까지 1씩 더해준다고 생각해보자.

 

0001111000 <-- 왼쪽 배열을 만드는데 반복문을 한번을 사용하여 만드는 방법이 있다.

 

누적합을 활용해서도 만들 수 있다.

000100-100 이런식으로 1로 만들 시작점과 끝나는점에 각각 1과 -1을 넣고 왼쪽부터 오른쪽으로 누적합을 구해가며 해당 인덱스까지의 누적합으로 갱신시켜주면

 

0001000-100

0001100-100

0001110-100

0001111-100

0001111000

 

위와같은 흐름으로 1을 채우는 것이 가능하다.

 

물론 위 케이스에서는 둘다 반복문을 한번씩 사용한다. 하지만 만약 이런 범위가 늘어난다고 생각해보자.

주어지는 구간의 수를 m , 배열의 크기를 n이라 생각한다면

 

반복문을 사용하는 방법은 m번 반복한다면 m * n 의 시간복잡도를 가지게 되지만 누적합은 마지막에 누적합 한번만 구해주면 되기에

m + n 의 시간복잡도를 가지게 된다.

 

 

 

문제를 푸는 방법은 아래와 같다.

 

1. 동영상 시간테이블을 배열로 저장한다. 1개의 인덱스를 1초라 생각한다.

ex 영상 길이가 1분이라면 60칸 크기의 배열을 만든다.

 

2. 사람들이 시청 기록의 시작기록과 마지막기록부분에 +1 , -1을 쌓아간다.

3. 누적합을 구한다.

4. 광고 시청구간만큼 합계를 구해나가면서 최다 시청구간을 구한다.

 

 

 

 

function solution(play_time, adv_time, logs) {
    
    const strToSeconds = (str) => {
        const [h,m,s] = str.split(":").map(v => +v)
        return h * 3600 + m * 60 + s
    }
    
    const fillZero = (num) => {
        return String(num).padStart(2,'0')
    }
    const secondsToStr = (seconds) => {
        const h = ~~(seconds/3600)
        const m = ~~(seconds%3600/60)
        const s =seconds%60
        return `${fillZero(h)}:${fillZero(m)}:${fillZero(s)}`
    }
    
    const timeTable = Array(strToSeconds(play_time)).fill(0)
    
    for (const time of logs){
        const [start,end] = time.split('-').map(v => strToSeconds(v))
        timeTable[start] += 1
        timeTable[end] -= 1
    }
    //누적합 계산
    let sum = 0
    for (let i = 0 ; i < timeTable.length ; i++){
        sum += timeTable[i]
        timeTable[i] = sum
    }
    
    const advTime = strToSeconds(adv_time)
    
    let curSum = 0
    for (let i = 0 ; i <advTime ; i++){
        curSum += timeTable[i]
    }
    let maxSum = curSum
    let ret = 0
    for (let i = 1 ; i < timeTable.length - advTime ; i++){
        curSum -= timeTable[i]
        curSum += timeTable[i+advTime]
        if (curSum >maxSum) {
            maxSum = curSum
            ret = i+1
        }
    }
    
    return secondsToStr(ret)
    
}