2021-11-25 15:40 작성
광고 재생구간 구하기
본 예시의 알고리즘은 실패 사례로 기록용으로 남겨둔 것이니 따라하지 않기를 바랍니다.
정의
동영상이 재생되는 동안 사용자들이 가장 많이 시청하는 구간에서 광고를 재생해야 한다. 사용자들의 누적 재생시간이 가장 많은 시청 구간에서 광고를 재생한다고 할 때 알고리즘을 구해보자(동영상 재생 시간, 광고 재생 시간, 시청자 로그 기록이 제공된다고 가정).
예시
- 동영상 재생 시간:
"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초 ~ 01시 45분 14초까지 광고를 재생하는 것이 가장 효과적이다.
실패 이유
- 가장 많이 겹치는 log 기록에서 기준값이 아닌 비교값 중 가장 많이 겹치는 log 구간이 최적의 광고 구간이라고 생각하고 설계했음.
- 그러나 이 설계는 광고의 재생시간과 기준값 log 위치가 최적의 위치일 때를 고려하지 않아 최적 구간이라고 할 수 없음.
개선방안
- 기준값 기준을 배제하지 않으면서 누적 adv_time이 가장 많이 나오도록 해야함.
- 가장 많이 겹치는 구간에서 각 log를 시작값으로 looping해 누적 adv_time이 가장 큰 곳을 시작 지점으로 삼으면 될 듯 함.
- 예를 들어 시작값(기준값)의 시작 시간과 종료 시간의 차가 광고 시간보다 클 경우 adv_time을 적용하고 그렇지 않을 경우 그 차를 적용한다. 그리고 이 기준값과 겹치는 다른 log의 겹치지 않는 앞 부분을 제외하고 겹치는 구간의 값만 구해 더한다. 총 더해진 값이 가장 큰 구간이 최적 광고 시간이 될 것이라고 생각한다.
- 해당 개선방안을 실패 2 항목에서 재현해봤으나 실패함.
결론
내가 상정한 조건은 다음과 같다.
- 첫째, 가장 많은 누적 시청자가 존재한다.
- 둘째, 가장 많은 누적 시청자가 존재하는 구간에서 누적 시청 시간이 가장 많은 구간을 선택한다. (이 때, 구간 선택은 시청자들 중 한 명의 시작 시간과 동일하게 설정)
그러나 내가 생각한 조건과 다르게 본 문제는 누적 재생시간을 1순위로 삼기에 다른 결과가 나오는 듯 하다. 만약 다시 풀어보게 된다면 이 부분을 상기해야 할 것 같다. 그럼에도 불구하고 내가 상정한 조건에서 알고리즘을 짜서 적용한다면 성능 개선을 통해 충분히 사용 가능할 것이라고 생각한다.
// 실패 알고리즘
function solution(play_time, adv_time, logs) {
var answer = find_adtime(play_time, adv_time, logs);
return answer;
}
function find_adtime (play_time, adv_time, logs) {
// 결과값
let adtime = "";
let parsed_logs = [];
// 시간을 추출해서 비교가능한 단위로 만들기(초 단위)
const { parsed_play, parsed_adv } = parse_play_adv(play_time, adv_time);
logs.forEach(log => {
let parsed = parse_log(log);
parsed_logs.push(parsed);
})
// 시간 순 정렬
parsed_logs.sort((a,b) => {
if (a[0] > b[0]) return 1;
if (a[0] < b[0]) return -1;
return 0;
})
// logs의 값들을 비교해 최적의 adtime 찾기
adtime = compare_logs(parsed_play, parsed_adv, parsed_logs);
return adtime;
}
function compare_logs (parsed_play, parsed_adv, parsed_logs) {
let subtr1 = 0;
let start_time = 0;
let count1 = 0;
for (let i=0; i < parsed_logs.length; i++) {
let count2 = 0;
let subtr2 = 0;
let longest_time = 0;
for (let k=i+1; k < parsed_logs.length; k++) {
// 비교값(k)가 기준값(i)의 범위 내에 있을 경우에만 허용
if (parsed_logs[i][0] <= parsed_logs[k][0] && parsed_logs[i][1] > parsed_logs[k][0]) {
count2 ++;
// console.log(count2);
const s = parsed_logs[i][1] - parsed_logs[k][0];
s > subtr2 ? (subtr2 = s, longest_time = parsed_logs[k][0]) : subtr2;
// console.log("기준값: ", parsed_logs[i], "범위값: ", parsed_logs[k]);
}
}
// 가장 많이 겹치는 구간을 찾고 비교값 시작 시간과 기준값 끝나는 시간의 차이가 가장 큰 시간을 찾아 적용함.
if (count2 > count1) {
count1 = count2;
if (subtr2 > subtr1) {
subtr1 = subtr2;
start_time = longest_time;
// console.log(start_time);
}
}
}
let hours = Math.floor(start_time / 3600);
if (hours < 10) hours = "0" + hours.toString();
let minutes = Math.floor((start_time - (hours * 3600)) / 60);
if (minutes < 10) minutes = "0" + minutes.toString();
let seconds = start_time - (hours * 3600) - (minutes * 60);
if (seconds < 10) seconds = "0" + seconds.toString();
//console.log(hours, ":", minutes, ":", seconds);
return `${hours}:${minutes}:${seconds}`
}
// 각 log의 시간을 string에서 초 단위로 변경
function parse_log (log) {
let parsed_log = [];
const regex = /[-]/;
let splited = log.split(regex);
splited.forEach(e => {
const regex2 = /[:]/
let splited_time_array = e.split(regex2);
let time = string_to_seconds(splited_time_array);
parsed_log.push(time);
})
return parsed_log;
}
// play_time과 adv_time의 string을 초 단위로 변경
function parse_play_adv (play_time, adv_time) {
const regex2 = /[:]/
let splited_play_time = play_time.split(regex2);
let splited_adv_time = adv_time.split(regex2);
let parsed_play_time = string_to_seconds(splited_play_time);
let parsed_adv_time = string_to_seconds(splited_adv_time);
return { parsed_play: parsed_play_time, parsed_adv: parsed_adv_time };
}
function string_to_seconds (array) {
let time =
parseInt(array[0]) * 60 * 60
+ parseInt(array[1]) * 60
+ parseInt(array[2]);
return time;
}
// 실패 2
function solution(play_time, adv_time, logs) {
var answer = find_adtime(play_time, adv_time, logs);
return answer;
}
function find_adtime (play_time, adv_time, logs) {
// 결과값
let adtime = "";
let parsed_logs = [];
// 시간을 추출해서 비교가능한 단위로 만들기(초 단위)
const { parsed_play, parsed_adv } = parse_play_adv(play_time, adv_time);
logs.forEach(log => {
let parsed = parse_log(log);
parsed_logs.push(parsed);
})
// 시간 순 정렬
parsed_logs.sort((a,b) => {
if (a[0] > b[0]) return 1;
if (a[0] < b[0]) return -1;
return 0;
})
adtime = compare_logs(parsed_play, parsed_adv, parsed_logs);
return adtime;
}
function compare_logs (parsed_play, parsed_adv, parsed_logs) {
let start_time = 0;
let count1 = 0;
let standard_time = 0;
for (let i=0; i < parsed_logs.length; i++) {
let count2 = 0;
let longest_time = 0;
let st = 0;
for (let k=i+1; k < parsed_logs.length; k++) {
// 비교값(k)가 기준값(i)의 범위 내에 있을 경우에만 허용
if (parsed_logs[i][0] <= parsed_logs[k][0] && parsed_logs[i][1] > parsed_logs[k][0]) {
count2 ++;
st = parsed_logs[i];
//console.log("기준값: ", parsed_logs[i], "범위값: ", parsed_logs[k]);
}
}
if (count2 > count1) {
count1 = count2;
standard_time = st;
}
}
const st_index = parsed_logs.findIndex(e => e === standard_time);
const st_array = parsed_logs.slice(st_index, st_index + count1 + 1);
// 광고 구간이 첫 기준 log보다 길 경우
if (st_array[0] !== undefined && (st_array[0][1] - st_array[0][0]) <= parsed_adv) {
start_time = st_array[0][0];
} else {
if (st_array[0] !== undefined) {
// 광고 구간이 첫 기준 log보다 짧다고 가정
let sum = 0;
for (let i=0; i < st_array.length; i++) {
let s_sum = 0;
const s_length = st_array[i][1] - st_array[i][0];
const adv_end = st_array[i][0] + parsed_adv;
// adv 재생 시간이 기준값 시청 종료 시간보다 짧을 경우
const adv_s_length = adv_end - st_array[i][0];
adv_end > st_array[i][1] ? s_sum += s_length : s_sum += adv_s_length;
for (let k=i+1; k < st_array.length; k++) {
// adv 재생 시간이 겹치는 구간에서도 재생될 경우
if (adv_end > st_array[k][0]) {
s_sum += adv_end - st_array[k][0];
}
}
// 가장 많이 겹치는 구간에서 누적 재생시간이 가장 긴 경우를 반환한다.
s_sum > sum && (sum = s_sum, start_time = st_array[i][0]);
}
};
}
let hours = Math.floor(start_time / 3600);
if (hours < 10) hours = "0" + hours.toString();
let minutes = Math.floor((start_time - (hours * 3600)) / 60);
if (minutes < 10) minutes = "0" + minutes.toString();
let seconds = start_time - (hours * 3600) - (minutes * 60);
if (seconds < 10) seconds = "0" + seconds.toString();
return `${hours}:${minutes}:${seconds}`
}
function parse_log (log) {
let parsed_log = [];
const regex = /[-]/;
let splited = log.split(regex);
splited.forEach(e => {
const regex2 = /[:]/
let splited_time_array = e.split(regex2);
let time = string_to_seconds(splited_time_array);
parsed_log.push(time);
})
return parsed_log;
}
function parse_play_adv (play_time, adv_time) {
const regex2 = /[:]/
let splited_play_time = play_time.split(regex2);
let splited_adv_time = adv_time.split(regex2);
let parsed_play_time = string_to_seconds(splited_play_time);
let parsed_adv_time = string_to_seconds(splited_adv_time);
return { parsed_play: parsed_play_time, parsed_adv: parsed_adv_time };
}
function string_to_seconds (array) {
let time =
parseInt(array[0]) * 60 * 60
+ parseInt(array[1]) * 60
+ parseInt(array[2]);
return time;
}