[JS] 광고 삽입 - 누적합의 활용 2

저번에 2차원 배열의 누적합을 다뤄봤었는데,

이미 카카오는 작년부터 누적합을 엄청 물어보고 있었네요.이 문제도 역시 누적합에 관한 문제입니다.

---

문제 요약

"죠르디"의 동영상 재생시간 길이 play_time, 공익광고의 재생시간 길이 adv_time, 시청자들이 해당 동영상을 재생했던 구간 정보 logs가 매개변수로 주어질 때, 시청자들의 누적 재생시간이 가장 많이 나오는 곳에 공익광고를 삽입하려고 합니다. 이때, 공익광고가 들어갈 시작 시각을 구해서 return 하도록 solution 함수를 완성해주세요. 만약, 시청자들의 누적 재생시간이 가장 많은 곳이 여러 곳이라면, 그 중에서 가장 빠른 시작 시각을 return 하도록 합니다.

 

[제한사항]

• play_time, adv_time은 길이 8로 고정된 문자열입니다.
  • play_time, adv_time은 HH:MM:SS 형식이며, 00:00:01 이상 99:59:59 이하입니다.
  • 즉, 동영상 재생시간과 공익광고 재생시간은 00시간 00분 01초 이상 99시간 59분 59초 이하입니다.
  • 공익광고 재생시간은 동영상 재생시간보다 짧거나 같게 주어집니다.
• logs는 크기가 1 이상 300,000 이하인 문자열 배열입니다.
  • logs 배열의 각 원소는 시청자의 재생 구간을 나타냅니다.
  • logs 배열의 각 원소는 길이가 17로 고정된 문자열입니다.
  • logs 배열의 각 원소는 H1:M1:S1-H2:M2:S2 형식입니다.
    • H1:M1:S1은 동영상이 시작된 시각, H2:M2:S2는 동영상이 종료된 시각을 나타냅니다.
    • H1:M1:S1는 H2:M2:S2보다 1초 이상 이전 시각으로 주어집니다.
    • H1:M1:S1와 H2:M2:S2는 play_time 이내의 시각입니다.
• 시간을 나타내는 HH, H1, H2의 범위는 00~99, 분을 나타내는 MM, M1, M2의 범위는 00~59, 초를 나타내는 SS, S1, S2의 범위는 00~59까지 사용됩니다. 잘못된 시각은 입력으로 주어지지 않습니다. (예: 04:60:24, 11:12:78, 123:12:45 등)
• return 값의 형식
  • 공익광고를 삽입할 시각을 HH:MM:SS 형식의 8자리 문자열로 반환합니다.

[입출력 예]

 

play_time	adv_time	logs	result
"02:03:55"	"00:14:15"	["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"]	"01:30:59"
"99:59:59"	"25:00:00"	["69:59:59-89:59:59", "01:00:00-21:00:00", "79:59:59-99:59:59", "11:00:00-31:00:00"]	"01:00:00"
"50:00:00"	"50:00:00"	["15:36:51-38:21:49", "10:14:18-15:36:51", "38:21:49-42:51:45"]	"00:00:00"

 

접근 방법

일단 logs가 30만 개이기 때문에, logs를 다루는 loop안에서 뭘 하려는 생각을 하면 안됩니다.

그래서 생각한 아이디어가 초 단위 시간의 누적합!

 

play_time의 최댓값은 99:59:59이기 때문에,

최댓값은 360,000초로 환산할 수 있습니다.

이 만큼의 배열을 만든 다음, logs를 순회하다가 특정 구간의 모든 값을 1 올려주면 되겠죠?

 

어라..? 많이 보던 문제 아닌가요?ㅎㅎ

2022.09.20 - [알고리즘] - [JS] 파괴되지 않은 건물: (new) 누적합

[JS] 파괴되지 않은 건물: (new) 누적합

 

구간 [0, 2]까지 1을 더하고 싶은 경우

[1, 0, 0, -1]라는 배열을 준비하고, 한번에 합해줍니다.

[1, 1, 1, 0]의 결과가 나오죠.

 

이 문제는 거기에서 약간 더를 요구합니다. 왜냐면 누적 시청자수를 구해야하니까요.

[1, 1, 1, 0]을 한 번 더 누적합을 해주면,

[1, 2, 3, 3]을 얻을 수 있고, arr[2]에 접근하면 최종 시청자 수인 3을 구할 수 있겠습니다.

정답 코드

function solution(play_time, adv_time, logs) {
    const playTime = makeTimeStamp(play_time);
    const advTime = makeTimeStamp(adv_time);
    const count = Array(playTime).fill(0);
    
    logs.forEach((log, i) => {
        const [start, end] = log.split("-").map(v => makeTimeStamp(v));
        count[start]++;
        count[end]--;
    });
    
    for (let i = 1; i <= playTime; i++) {
        count[i] += count[i - 1];
    }
    
    for (let i = 1; i <= playTime; i++) {
        count[i] += count[i - 1];
    }
    
    let sum = count[advTime - 1];
    let result = 0;
    
    for(let i = advTime - 1; i < playTime; i++) {
        if(sum < count[i] - count[i - advTime]) {
            sum = count[i] - count[i - advTime];
            result = i - advTime + 1;
        }
    }
    
    return makeTimeString(result);
}

function makeTimeStamp(timestring) {
    const [hour, min, sec] = timestring.split(":").map(v => Number(v));
    return hour * 3600 + min * 60 + sec;
}

function makeTimeString(timestamp) {
    let currTimeStamp = timestamp;
    const hour = String(Math.floor(currTimeStamp / 3600));
    currTimeStamp = currTimeStamp % 3600;
    
    const min = String(Math.floor(currTimeStamp / 60));
    const sec = String(currTimeStamp % 60);
    return `${"0".repeat(2 - hour.length) + hour}:${"0".repeat(2 - min.length) + min}:${"0".repeat(2 - sec.length) + sec}`;
}

 

팁 1. 누적합 offset 배열 구하기 + 누적합 * 2번 하기

logs.forEach((log, i) => {
        const [start, end] = log.split("-").map(v => makeTimeStamp(v));
        count[start]++;
        count[end]--;
    });
    
    for (let i = 1; i <= playTime; i++) {
        count[i] += count[i - 1];
    }
    
    for (let i = 1; i <= playTime; i++) {
        count[i] += count[i - 1];
    }

 

양 끝 값만 +1, -1로 조작해주면 됩니다.

그리고 두 번 합을 진행해서 최종 누적 시청자수를 만들어줍시다.

 

팁 2. 광고 시작 위치 삽입 + sum 비교

let sum = count[advTime - 1];
    let result = 0;
    
    for(let i = advTime - 1; i < playTime; i++) {
        if(sum < count[i] - count[i - advTime]) {
            sum = count[i] - count[i - advTime];
            result = i - advTime + 1;
        }
    }

 

count가 광고에 상관없이 모든 값이 끝까지 더해졌기 때문에,

sum을 비교할 때는 advTime 기준으로 count의 양 끝값의 차를 기준으로 비교해줍니다.

 

 

---

이 기업 요즘 누적합에 빠져있나요..?

그럼 이만!