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

문제

카카오TV에서 유명한 크리에이터로 활동 중인 죠르디는 환경 단체로부터 자신의 가장 인기있는 동영상에 지구온난화의 심각성을 알리기 위한 공익광고를 넣어 달라는 요청을 받았습니다. 평소에 환경 문제에 관심을 가지고 있던 "죠르디"는 요청을 받아들였고 광고효과를 높이기 위해 시청자들이 가장 많이 보는 구간에 공익광고를 넣으려고 합니다. "죠르디"는 시청자들이 해당 동영상의 어떤 구간을 재생했는 지 알 수 있는 재생구간 기록을 구했고, 해당 기록을 바탕으로 공익광고가 삽입될 최적의 위치를 고를 수 있었습니다.
참고로 광고는 재생 중인 동영상의 오른쪽 아래에서 원래 영상과 동시에 재생되는 PIP(Picture in Picture) 형태로 제공됩니다.

"죠르디"의 동영상 재생시간 길이 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"

풀이

2021 카카오 블라인드 테스트에서 출제된 문제이다. 카카오 코딩테스크 답게(?) 상당한 지문과 복잡한 이미지가 눈을 어지럽히는게 시작 전부터 난이도가 상당해보인다. 또 카카오답게(?) 시간 처리와 관련된 문제이다. 시간과 관련해서는 항상 신경써야 할 점이 있는데, 이에 대한 자세한 내용은 해당 포스트에서 참고할 수 있다. 3단계에 랭크가 되어있지만 다른 3단계 문제들과 비교했을때 조금 더 어려운 난이도의 문제라고 생각한다. 실제 카카오 해설을 보아도 정답률이 1.23%로 매우 낮은 수치를 보이고 있다. 그러나 사실 문제 접근 방식을 이해할 수 있다면 정답률에 비해 그렇게까지 어려운 문제는 아니다. 비교적 간단한 알고리즘과 구현 역시 용이하기 때문이다. 하나씩 살펴보도록 하자.

시간 변환 함수

시간과 관련한 문제에서 주어진 시간이 시:분:초의 형태로 주어진다면 보통 가장 작은 단위로 변환하여 계산하는 것이 편리한 경우가 많다. 숫자의 단위가 커지겠지만, 하나의 단위로 시간부터 초까지 모두 표현할 수 있기 때문이다. 이전 포스팅에서는 가장 작은 시간 단위가 milliseconds였기 때문에 milliseconds로 바꿔주었지만, 여기서는 초(seconds)가 가장 작은 단위이므로 입력된 시간을 초(seconds) 단위로 변환하는 함수를 하나 제작해주자. 문제 조건에 의해 입력되는 시간의 형태는 항상 HH:MM:SS이기 때문에 다음과 같이 구현할 수 있다.

// HHMMSS의 각 원소는 문자열이라는 것에 주의하자
// 때문에 초단위(HHMMSS[2]) 역시 1을 곱해 정수형으로 변환이 필요하다.
const calculateTime = (time) => {
  const HHMMSS = time.split(':');
  const amount = HHMMSS[0]*3600 + HHMMSS[1]*60 + HHMMSS[2]*1;
  return amount;
}

이때 문제에서 요구하는 정답은 다시 HH:MM:SS 형식인 것을 알 수 있다. 따라서 계산을 마치고 도출된 결과를 다시 위의 형태로 바꾸어주는 함수 역시 필요하다. 다음과 같이 해당 함수를 구현해주자.

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}`
}

누적 재생 시간 최다 구간

문제에서 요구하는 것은 주어진 play_time 동안에 광고 시간이 adv_time 만큼 방영될 때 시청 시간 logs를 받아 누적 재생 시간이 가장 많이 나오는 구간의 시작 시간이다.

광고의 시간은 일정하고, 모든 play_time 중에 딱 한 번 삽입되기 때문에 누적 재생 시간이 가장 크게 나타나기 위해서는 가장 많은 시청자가 몰리는 시간대가 필요하다.

앞서 카카오 코딩테스트 '추석 트래픽'에서도 비슷하게 사용자가 가장 많이 몰리는 구간을 구해 초당 최대 처리량을 구한 적이 있다. 이 문제 역시 이와 유사한 면모를 보이지만 살짝 다른 부분이 있다. 바로 구간별로 시청자의 누적 시청 수가 필요하다. 이는 시청자가 가장 많이 몰리는 시간대가 문제 조건에 의해 최소 2개 이상 등장할 수 있고, 이 경우에는 더 빨리 시작하는 시간을 리턴해야 하기 때문이다. 즉 우리는 단순히 최다 누적 시청 횟수를 구하는게 아닌 구간별 시청횟수와 최다 누적 시청 횟수를 구해주어야 한다.

때문에 문제에서 주어진 play_time 을 전체 구간으로 만들어주자. 최댓값은 99:59:59이기 때문에 이를 초 단위로 환산하면 360000을 넘지 않는 것을 알 수 있다. 따라서 주어진 play_time을 초단위로 환산한 크기만큼의 times 배열을 선언하고, 이 배열을 전체 방송의 전체 구간으로 사용하도록 하자. 이때 logs는 시청자들의 시청시작시간 - 시청종료시간을 담고 있으므로 이를 이용해서 전체 구간에서 어느 시간에 시청이 시작되고 종료되는지를 체크할 수 있다. 다음과 같이 구현해주자.

// play_time을 초단위로 환산하고
const pt = calculateTime(play_time);
// 이 크기만큼의 전체 구간 배열을 생성하여 0으로 초기화
const times = new Array(pt).fill(0);

logs.forEach(log => {
  // 시청 시작시간과 종료시간으로 구분
  const [start, end] = log.split('-');
  // 해당 시간을 모두 초단위로 변환
  const ws = calculateTime(start);
  const we = calculateTime(end);
  // 시작시간 구간에 입성할 때는 +1, 다시 나올때는 -1
  times[ws]++;
  times[we]--;
}

위 과정을 통해 전체 구간 times 배열에는 특정 시간대에 시청이 시작되었으면 1이상의 값이 들어있을 것이고, 시청을 마치고 종료하는 시간대에는 -1 이하의 값이 들어있게 될 것이다. 즉 다음과 같은 결과를 얻을 수 있다.

• [0, 0, 0, 1, 0, 0, -1, 0, 0, 1, 0, -1, 0]

위 예시의 경우 1의 값이 시청을 시작한 시간이고, -1의 값이 시청을 종료한 시간을 의미한다. 하지만 이는 단순히 시청 시작/종료를 구분하는 값일뿐 어느 구간에 얼마의 시청횟수가 있었는지는 아직 알 수 없다. 따라서 위 배열을 가지고 누적 시청 횟수를 구해주도록 하자.

누적합(구간합)

현재 시청 시작과 종료 구간이 기록된 times 배열을 가지고 있다. 이를 가지고 어떻게 최다 누적 시간을 구해줄 수 있을까? 다음 표를 보자.

	1초	2초	3초	4초	5초	6초	7초	8초	9초	10초
a		1						-1
b			1				-1
c		1								-1
times	0	2	1	0	0	0	-1	-1	0	-1

a, b, c 세 사람의 시청기록에 의해 다음과 같이 구간 기록이 만들어졌을 것이다. 따라서 2초에는 2명이 시청을 시작했고, 3초에는 1명이 시청을 시작했으며, 이들은 각각 7초와 8초 그리고 10초에 시청을 종료했다.

이때 특정 구간의 누적 시청자 수를 구하기 위해서는 이전 값과 현재 값을 더해주면 되는 것을 알 수 있다. 종료하는 구간의 값이 -1이기 때문에 이전 값과 다음 값을 더해주는 것을 계속 하면 구간 내 시청자 수를 파악할 수 있기 때문이다. 이는 위에 링크를 건 '추석 트래픽' 문제에서도 유사하게 사용하는 방식이다. 이를 수행하고 나면 다음과 같다.

	1초	2초	3초	4초	5초	6초	7초	8초	9초	10초
times	0	2	1	0	0	0	-1	-1	0	-1
시청자수	0	2	3	3	3	3	2	1	1	0

따라서 2초 구간에는 2명의 시청자가, 3초 - 6초까지는 3명의 시청자가 있다는 사실을 파악할 수 있다. 그러나 시청자의 수는 재생 횟수를 말하는 것이 아니기 때문에, 누적 재생 횟수를 다시 구해주어야 한다. 이 역시 간단하다. 앞서 누적합 방식으로 구한 것과 마찬가지로 현재 배열에 다시 누적합을 적용하면 누적 재생 횟수를 구할 수 있다. 누적 재생 횟수라는 것은 결국 시청자 수에 의해 결정되기 때문이다. 따라서 다음과 같은 결과가 된다.

	1초	2초	3초	4초	5초	6초	7초	8초	9초	10초
times	0	2	1	0	0	0	-1	-1	0	-1
시청자수	0	2	3	3	3	3	2	1	1	0
누적 재생횟수	0	2	5	8	11	14	16	17	18	18

따라서 우리는 어떤 시간 값이 주어졌을 때, 그에 해당하는 누적 재생수를 파악할 수 있다. 이를 누적합을 이용해 구해주는 코드는 다음과 같이 구현할 수 있다.

// 시청자 수 누적합으로 구하기
for(let i = 1; i <= pt; i++)
  times[i] += times[i-1];

// 누적 재생횟수 누적합으로 구하기
for(let i = 1; i <= pt; i++)
  times[i] += times[i-1];

최다 누적 재생 시간

구간별 누적 재생횟수까지 구해주었다면, 이를 이용해 최다 누적 재생이 일어난 구간을 구해줄 수 있다. 다시 위에서 만들어준 표를 예시로 들어보자. 위의 경우엔 play_time이 총 10초로 주어진 경우이다. 이때 adv_time이 4초라면 다음과 같은 구간을 탐색하게 될 것이다.

1. 1초 - 4초
2. 2초 - 5초
3. 3초 - 6초
4. 4초 - 7초
5. 5초 - 8초
6. 6초 - 9초
7. 7초 - 10초

그리고 각 구간별로 누적 재생 횟수가 최대가 되는 구간이 정답이 될 것이다. 이 구간별 누적 재생 횟수는 다음과 같이 구해줄 수 있다.

• 광고 종료 시간 - 광고 시작 시간

즉 1번의 경우는 times[3] - times[0] = 8이 되고, 2번의 경우는 times[4] - times[1] = 9로 구할 수 있다. 이때 문제 조건에 의해 1초부터 시간이 시작되지만, 배열의 인덱스는 0부터 시작하므로 시간값에 -1을 통해 접근해야 하는 것을 주의하자.

따라서 초기 최다 누적 재생 횟수는 times[광고시간-1]이 될 것이다. 그리고 우리가 구하려는 값은 최대 누적 재생 횟수 구간이 되는 값의 시작시간이므로 이는 우리가 접근하는 배열의 인덱스를 통해 구해줄 수 있다. 배열의 인덱스는 모두 1초 단위의 구간이 되기때문에, 현재 구간보다 더 큰 누적 재생횟수 구간이 나오면 누적 재생 횟수 값과 인덱스 값을 모두 갱신해주도록 하자. 이때 누적 재생 시간이 최대인 경우가 여러 곳일 수 있기 때문에, 항상 큰 경우에만 값을 갱신해주어야 한다. 배열의 인덱스를 1씩 늘려가며 접근할 것이므로 자연스레 가장 빠른 시작 시간을 구해줄 수 있다.

// adv_time을 초단위로 변환
const at = calculateTime(adv_time);
// 초기 최다 누적 재생 횟수 = times[광고 종료 시간-1];
let sum = times[at-1];
// 초기 인덱스(= 시작 시간) = 0
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는 위에서 초기값을 at-1로 접근하기에
    // 정상적인 시간 출력을 위해 다시 +1을 해주어야 한다.
    // 이때의 idx는 갱신된 최다 누적 재생 횟수 구간의 시작값으로 곧 시작 시간과 동일
    idx = i - at + 1;
  }
}

return formatterTime(idx);

전체코드

누적합(구간합)을 이용해 풀이하는 문제라는 점을 캐치했다면 비교적 쉽게 문제를 풀 수 있었을 것이고, 그렇지 않다면 매우 어렵게 다가왔을 문제이다. 역시 알고리즘 문제는 접근 방법을 파악하는 게 반 이상은 먹고 들어가는 것 같다. 다음은 주석을 제외한 전체 코드이다.

function 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];
  
  let sum = times[at-1];
  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);
               
}

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;
  
  HH = HH > 9 ? HH : '0' + HH;
  MM = MM > 9 ? MM : '0' + MM;
  SS = SS > 9 ? SS : '0' + SS;
  
  return `${HH}:${MM}:${SS}`
}

출처

https://programmers.co.kr/learn/courses/30/lessons/72414