[프로그래머스 lev3/JS] 광고 삽입

문제 출처

프로그래머스 lev3 - 광고 삽입

나의 풀이 (실패)

최대값이 99:59:59이므로 초단위로 환산하면 360,000인데
360,000을 O(n)으로 하면 너무 큰 게 아닌가 라고 겁먹었다.

다른 풀이

누적합 + 완전탐색

누적합이 아직 감이 안 온다..

times 배열을 채울 때, 나는 모든 배열 요소에 1을 더하고 빼고를 반복했다. 반면 아래 풀이는 시작 구간에만 1을 더해주고 빠져 나올 때만 1을 빼주는 식으로 times 배열을 구성했다.

누적합을 통해 이전 배열 요소를 현재 배열 요소에 더해주면,
현재 배열 요소에는 시간별 시청자 수가 담기게 된다.

여기에서 한번 더 누적합을 통해 이전 배열 요소를 현재 배열 요소에 더해주면,
현재 배열 요소에 누적 재생횟수가 담기게 된다.
times 배열의 index는 재생 타임라인이 된다.

for문을 돌면서 광고 시간이 최대가 되는 경우를 찾아서 반환한다.

const calculateTime = (time) => {
  const HHMMSS = time.split(':')
  const amount = HHMMSS[0]*3600 + HHMMSS[1]*60 + HHMMSS[2]*1
  return amount
}

const formatterTime = (time) => {
  let HH = time / 3600 >> 0
  let MM = (time / 60 >> 0) % 60
  let SS = time % 60
  
  // 1자리 숫자면 앞에 0을 붙이기 
  HH = HH > 9 ? HH : '0' + HH
  MM = MM > 9 ? MM : '0' + MM
  SS = SS > 9 ? SS : '0' + SS
  
  return `${HH}:${MM}:${SS}`
}

const solution = (play_time, adv_time, logs) => {
  const pt = calculateTime(play_time)
  const at = calculateTime(adv_time)
  const times = new Array(pt).fill(0)
  
  logs.forEach(log => {
    const [start, end] = log.split('-')
    const ws = calculateTime(start)
    const we = calculateTime(end)
    times[ws]++ // 시작시간 구간 진입시 ++
    times[we]-- // 끝나면 -- 
  })
  
  // 시간별 시청자 수 (누적합)
  for(let i = 1; i <= pt; i++)
    times[i] += times[i-1]
  // 누적 재생횟수 (누적합)
  for(let i = 1; i <= pt; i++)
    times[i] += times[i-1]
  
  // 초기값을 00:00:00 으로 설정하므로 : "00:00:00 + 광고시간(at) == times[at-1]"
  let sum = times[at-1]
  // 초기 index 값(누적 재생 시간)
  let idx = 0
  
  
  for(let i = at-1; i < pt; i++) {
    if(sum < times[i] - times[i-at]) { // 최대값이 여러 개일 수 있으므로, 큰 경우에만 업데이트
      sum = times[i] - times[i-at] // 광고재생시간
      idx = i - at + 1
    }
  }
  
  return formatterTime(idx)
               
}

console.log(
  solution("02:03:55", "00:14:15", [
    "01:20:15-01:45:14",
    "00:25:50-00:48:29",
    "00:40:31-01:00:00",
    "01:37:44-02:02:30",
    "01:30:59-01:53:29",
  ])
); // "01:30:59"

string to int 와 int to string

const stoi = (str) => { // 시:분:초 => 초
  const ss = str.substring(6,8)
  const mm = str.substring(3,5)
  const hh = str.substring(0,2)

  return (hh*60*60) + (mm*60) + (ss*1)
}

const itos = (int) => { // 초 => 시:분:초 
  let ss = int % 60 
  int /= 60
  let mm = (int >> 0) % 60 
  int /= 60 
  let hh = (int >> 0)

  hh = hh > 9 ? hh : '0' + hh 
  mm = mm > 9 ? mm : '0' + mm 
  ss = ss > 9 ? ss : '0' + ss 

  let res = ''
  res += hh 
  res += ':'
  res += mm 
  res += ':'
  res += ss 
  
  return res 
}

다른 풀이 2

누적합 + 슬라이딩 윈도우

풀이 원리는 비슷하다.

슬라이딩 윈도우란 윈도우(특정범위)가 있을 때, 윈도우 내부 요소의 값을 사용해 문제를 푸는 알고리즘이다.

이번 문제가 광고시간을 찾는 것이다 보니 슬라이딩 윈도우로 풀기 좋다. 구간 단위로 움직이다 보니, 완전탐색보다 빠르다.

완전탐색의 시간복잡도를 줄여줄 수 있는 선택지들

• 누적합, 투포인터, 슬라이딩 윈도우 등

const stoi = (str) => { // 시:분:초 => 초
  const ss = str.substring(6,8)
  const mm = str.substring(3,5)
  const hh = str.substring(0,2)

  return (hh*60*60) + (mm*60) + (ss*1)
}

const itos = (int) => { // 초 => 시:분:초 
  let ss = int % 60 
  int /= 60
  let mm = (int >> 0) % 60 
  int /= 60 
  let hh = (int >> 0)

  hh = hh > 9 ? hh : '0' + hh 
  mm = mm > 9 ? mm : '0' + mm 
  ss = ss > 9 ? ss : '0' + ss 

  let res = ''
  res += hh 
  res += ':'
  res += mm 
  res += ':'
  res += ss 
  
  return res 
}

const solution = (play_time, adv_time, logs) => {
  let cnt = Array(360_000).fill(0)
  
  let end = stoi(play_time)
  let adv = stoi(adv_time)

  let answer = 0
  let sum = 0 

  logs.forEach((log) => {
    let s = stoi(log.substring(0,8))
    let e = stoi(log.substring(9))

    cnt[s]++
    cnt[e]-- 
  })

  // 누적합 
  for(let i=0; i<end-1; ++i) cnt[i+1] += cnt[i]

  // 재생시간 윈도우 
  for(let i=0; i<adv; ++i) sum += cnt[i]

  let maxSum = sum 
  for(let i=adv; i<end; ++i){
    // 한칸씩 슬라이딩 
    sum -= cnt[i-adv]
    sum += cnt[i]

    if(sum > maxSum){
      maxSum = sum 
      answer = i - adv + 1
    }
  }

  return itos(answer)
}

참고

[프로그래머스] LV.3 광고 삽입 (JS)
[c++][프로그래머스] 광고 삽입