[JS] 광고 삽입

문제

프로그래머스

 

풀이

이 문제는 누적합 알고리즘을 이용한 문제이다.

 

처음에는 어떤 알고리즘을 적용해야할지 의문이 들었다. 처음에는 DP 알고리즘을 이용해 각 시간을 초 단위로 구분해 시청자를 구했다. 그렇지만 이 문제는 시청자 수를 구하는 문제가 아닌 가장 많은 시청 시간을 갖는 시간대를 구하는 문제이다.

 

결국 누적합 알고리즘을 적용해 기존에 구해둔 시청자수를 이용해 누적 시청 시간을 구했다.

 

이 문제와 같이 자료의 수는 많아 2중 반복을 할 수 없으며, 이전까지의 결과값이 필요하고 범위가 지정되어 있는 문제의 경우는 누적합 알고리즘을 이용한 접근법 설계를 학습할 수 있었다.

 

코드

const solution = (play_time, adv_time, logs) => {
  const calcTime = (time) => {
    const [h, m, s] = time.split(":");
    const newTime = h * 3600 + m * 60 + s * 1;
    return newTime;
  };

  const format = (time) => {
    const h = (time / 3600) >> 0;
    const m = ((time / 60) >> 0) % 60;
    const s = time % 60;
    return `${h > 9 ? h : "0" + h}:${m > 9 ? m : "0" + m}:${
      s > 9 ? s : "0" + s
    }`;
  };

  const totalPlayTime = calcTime(play_time);
  const adTime = calcTime(adv_time);
  const ary = Array.from({ length: totalPlayTime }, () => 0);

  for (let log of logs) {
    const [st, end] = log.split("-").map((e) => calcTime(e));
    ary[st] += 1;
    ary[end] -= 1;
  }

  for (let i = 1; i < ary.length; i++) {
    ary[i] += ary[i - 1];
  }
  for (let i = 1; i < ary.length; i++) {
    ary[i] += ary[i - 1];
  }

  let answer = 0;
  let sum = ary[adTime - 1];

  for (let i = adTime - 1; i <= ary.length; i++) {
    const ad = ary[i] - ary[i - adTime];
    if (ad > sum) {
      sum = ad;
      answer = i - adTime + 1;
    }
  }

  return format(answer);
};