programmers. 광고 삽입

문제

문제

코딩테스트 연습 - 광고 삽입

풀이

추석 트래픽 문제와 동일하다고 생각해서 같이 풀었는데 시간 초과가 걸려버렸다

programmers. 추석 트래픽

풀이를 찾아보니 투 포인터, 슬라이딩 윈도우를 사용하여 풀어야하는데

나는 존재 조차 몰랐지만 추석 트래픽에서는 배열의 크기가 너무 커서 일반적인 슬라이딩 윈도우 방식으로는 풀 수가 없었다고 한다..

기본적인 풀이는 죠르디의 영상 시간 만큼의 크기를 가진 배열을 모두 0으로 초기화하고 사람이 재생한 구간은 1씩 늘린다

그 배열을 투 포인터 방식으로 순회하며 가장 높았던 구간을 찾는 것

초 변환

역시나 이런 문제는 시간, 분, 초 단위를 모두 초로 환산해서 계산하는 것이 편하다

        function transTime(time, option = true){
            if(option){
                const [h,m,s] =time.split(':');
                return h*3600 + m*60 + s*1;
            }
            const h = Math.floor(time/3600).toString();
            const m = Math.floor((time%3600)/60).toString();
            const s = Math.floor(((time%3600)%60)%60).toString();
            return `${h.length===1 ? '0'+h : h}:${m.length===1 ? '0'+m : m}:${s.length===1 ? '0'+s : s}`
        }

true/false의 option 값을 주어서 시간 -> 초, 초 -> 시간 모두 구현하여 하나의 함수에 묶어서

나중에 정답을 리턴할 때도 사용할 수 있도록 했다

배열 초기화

    const viewer = Array(playTime+1).fill(0);

    logs.forEach((log) => {
        const [start, end] = log.split('-').map(v=>transTime(v));
        viewer[start]++;
        viewer[end]--;
    });

    for(let i=1;i<=playTime;i++) viewer[i] += viewer[i-1];

재생 크기 만큼 0으로 초기화한 배열에

주어진 재생 구간, log를 초 단위로 바꾼 뒤 시작부분을 1늘리고, 종료시점을 1줄인다

그 뒤 배열 인덱스 1부터 i값 = i값 + i-1의 값 하면 재생 구간의 누적 수를 구할 수 있다

가장 놀라웠던 코드 나는 죽었다 깨어나도 이런 수학적 사고는 스스로 할 수 없을텐데.. 노력해야겠다

투 포인터

        while (right<playTime){
            time -= viewer[left];
            time += viewer[right];
            if(time>max){
                max = time;
                start = left+1;
            }
            left++;
            right++;
        }

0부터 광고 시간만큼 미리 값을 구한 뒤 투 포인터로 배열 마지막까지 순회하는 코드다

전체 코드

function solution(play_time, adv_time, logs) {
    if(play_time===adv_time) return '00:00:00';
    const minAdv = transTime(adv_time);
    const playTime = transTime(play_time);

    const viewer = Array(playTime+1).fill(0);

    logs.forEach((log) => {
        const [start, end] = log.split('-').map(v=>transTime(v));
        viewer[start]++;
        viewer[end]--;
    });

    for(let i=1;i<=playTime;i++) viewer[i] += viewer[i-1];

    let time = 0;
    for(let i=0; i<minAdv;i++) time += viewer[i];

    let [left,right] = [0,minAdv];
    let max = time;
    let start= 0;

    while (right<playTime){
        time -= viewer[left];
        time += viewer[right];
        if(time>max){
            max = time;
            start = left+1;
        }
        left++;
        right++;
    }

    return transTime(start,false);

    function transTime(time, option = true){
        if(option){
            const [h,m,s] =time.split(':');
            return h*3600 + m*60 + s*1;
        }
        const h = Math.floor(time/3600).toString();
        const m = Math.floor((time%3600)/60).toString();
        const s = Math.floor(((time%3600)%60)%60).toString();
        return `${h.length===1 ? '0'+h : h}:${m.length===1 ? '0'+m : m}:${s.length===1 ? '0'+s : s}`
    }
}