광고 삽입
📚 문제 설명
전체 동영상의 길이가 play_time 으로 주어지며 해당 동영상 사이에 adv_time 길이의 광고를 넣고자 한다.
해당 동영상을 시청하는 시청자들의 시청 시간을 logs 로 주어진다.
이 때 광고의 누적 재생 시간이 최대가 될 때는 광고를 언제 시작해야하는가.
예시
play_time: 02:03:55
adv_time: 00:14:15
logs: ["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"]
👨🏻💻 풀이 과정
이 문제는 특정 구간에서 그 합이 최대가 되는 구간을 찾는 문제이다.
따라서 이 문제는 누적합을 이용할 것이며, 전체 재생 시간 play_time 을 초 단위로 변경하여 그 길이만큼의 배열을 만들 것이다.
그 후 log 를 확인하여 시청자가 시청을 시작하는 시간에 +1, 시청 종료 시간에 -1을 하여 누적합을 진행한다.
그럼 아래표와 같이 진행될 것이다.
| 0초 | 1초 | 2초 | 3초 | 4초 | |
|---|---|---|---|---|---|
| 원래 배열 | 0 | 1 | 0 | -1 | 0 |
| 누적합 | 0 | 1 | 1 | 0 | 0 |
| 누적합 2 | 0 | 1 | 2 | 2 | 2 |
이 표를 보면 누적합을 1번 진행했을 때는 각각의 시간에 시청자가 몇명 보고 있는지 알 수 있다.
그리고 누적합을 한번 더 진행했을 경우
각각의 시간에 누적 재생시간 이 나오게 된다.
따라서 전체 로직은 다음과 같이 만들었다.
logs를 확인.- 시작시간에 +1, 종료시간에 -1.
- 누적합 2회 진행.
adv_time길이의 구간합이 최대가 되는 구간 확인.- 결과 출력.
전체 풀이
function solution(play_time, adv_time, logs) {
var answer = '';
// 초단위로 변경
const TurnToSeconds = (input) => {
const TimeArr = input.split(':').map(Number);
let times = 0;
TimeArr.forEach((Value, Index) => {
times += Value * (60 ** (2 - Index));
});
return times;
};
// 전체 시간
const PlaySeconds = TurnToSeconds(play_time);
// 광고 시간
const AdvSeconds = TurnToSeconds(adv_time);
// 전체 시간 배열 (초단위)
let TimeLine = new Array(PlaySeconds).fill(0);
// 시청자 시청 시간 기록.
logs.forEach(v => {
const [Start, End] = v.split('-');
const StartSeconds = TurnToSeconds(Start);
const EndSeconds = TurnToSeconds(End);
// 시청 시작 시간에 +1
TimeLine[StartSeconds] += 1;
// 시청 종료 시간에 -1
TimeLine[EndSeconds] -= 1;
});
// 누적합 1회
for (let i = 1; i < TimeLine.length; i++) {
TimeLine[i] += TimeLine[i - 1];
}
// 누적합 2회
for (let i = 1; i < TimeLine.length; i++) {
TimeLine[i] += TimeLine[i - 1];
}
// 0초에 광고를 재생했을 때의 값으로 초기화.
let max = TimeLine[AdvSeconds - 1];
// 0초에 광고를 재생했을 때.
let AdvStart = 0;
// 구간합이 최대가 되는 구간을 찾는다.
for (let i = AdvSeconds - 1; i < TimeLine.length; i++) {
if (max < TimeLine[i] - TimeLine[i - AdvSeconds]) {
max = TimeLine[i] - TimeLine[i - AdvSeconds];
// 광고는 1초부터다. 따라서 마지막에 1초를 더해야함.
AdvStart = i - AdvSeconds + 1;
}
}
// 시간(초)을 정답에 맞는 형태로 변경.
const LocalScale = (StartSeconds) => {
let Seconds = StartSeconds % 60;
let Minutes = Math.floor(StartSeconds / (60)) % 60;
let Hours = Math.floor(StartSeconds / (60 ** 2));
// padStart를 이용해 2자릿수로 표기되도록 수정.
answer = `${Hours.toString().padStart(2, '0')}:${Minutes.toString().padStart(2, '0')}:${Seconds.toString().padStart(2, '0')}`;
};
LocalScale(AdvStart);
return answer;
}
🧐 후기
배열을 초단위의 길이로 만들면 최대 360,000의 길이의 배열이 만들어지는데 이것이 싫어서 고민하다가 결국 다른 사람들의 풀이를 확인했다. 그런데 다른 사람들 모두 그냥 재생 시간 만큼의 배열을 만드는 것을 확인하고 그제서야 누적합을 이용하여 문제를 풀었다.
백준 문제에서의 기본을 128mb라고 생각하면 1.3억 바이트이기 때문에 배열의 360,000의 길이로 고민할 이유가 없었던 것 같다.
