[프로그래머스]광고 삽입 (C++ / 2021 KAKAO BLIND)

광고 삽입 (Level 3)

문제

전체 문제 보기

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

접근법

주어진 문제에서 동영상의 최대 길이는 99시간 59분 59초입니다. 이를 초로 변환하면 360,000 개의 시간이 존재합니다. 각 초마다 시청자 수를 계산한 뒤 최대 시청 구간을 sliding window 알고리즘으로 탐색하여 해결할 수 있는 문제입니다. sliding window 알고리즘은 two pointer 알고리즘과 흡사하며 two pointer 알고리즘과는 다르게 탐색 구간이 일정하다는 특징이 있습니다. (two pointer 알고리즘 설명 보기)

구현

먼저 string 타입의 시간을 int 타입의 시간(초) 변환하고 int 타입의 시간(초)를 string 타입으로 변환하는 함수를 살펴보겠습니다.

int StrToInt(const string& str)
{
    int h{}, m{}, s{};
    h = atoi(str.substr(0, 2).c_str());
    m = atoi(str.substr(3, 2).c_str());
    s = atoi(str.substr(6, 2).c_str());

    return (h * 3600) + (m * 60) + s;
}

string IntToStr(int sec)
{
    int h, m, s;
    h = sec / 3'600;
    sec -= h * 3'600;
    m = sec / 60;
    sec -= m * 60;
    s = sec;

    string hh, mm, ss;
    if (h < 10) hh + "0";
    hh + to_string(h);

    if (m < 10) mm + "0";
    mm + to_string(m);

    if (s < 10) ss + "0";
    ss + to_string(s);

    return hh + ":" + mm + ":" + ss;
}

다음으로 0초 부터 동영상이 끝날 때까지 각 시간 별 시청자 수를 담는 배열을 totalViewers를 다음과 같이 정의하고 데이터를 입력합니다.

    // totalViewers[sec]: sec 초에 영상을 시청중인 사람 수,
    // size: 전체 동영상 길이 + 1
    // 초기값: 모든 원소 0으로 초기화
    vector<int> totalViewers(playLen + 1, 0);

    // totalViewers 배열에 시청기록 입력
    for (string log : logs)
    {
        int start = StrToInt(log.substr(0, 8));
        int end = StrToInt(log.substr(9, 8));
        // log의 시청 시작 시간 부터 시청 종료시간 까지 시청자 수 ++
        for (int sec = start; sec < end; sec++)
            totalViewers[sec]++;
    }

다음으로 큐를 이용하여 전체 구간을 탐색하며 광고 시청자 수가 최대인 구간을 찾습니다. 이때 큐를 이용한 sliding window를 사용하여 계산할 수 있습니다.

    // 큐를 이용한 sliding window 알고리즘
    queue<int> q;

    long long adViewers{}; // 현재 구간 광고 시청자수  
    long long maxAdViewers{}; // 광고 시청자수가 최대인 구간의 시청자 수
    int answerSec{};          // 광고 시청자수가 최대인 구간 시작점

    for (int sec = 0; sec < advLen; sec++)
    {
        adViewers += totalViewers[sec];
        q.push(totalViewers[sec]);
    }

    maxAdViewers = adViewers;
    answerSec = 0;

    for (int sec = advLen; sec < playLen; sec++)
    {
        adViewers += totalViewers[sec];
        q.push(totalViewers[sec]);

        adViewers -= q.front();
        q.pop();

        if (maxAdViewers < adViewers)
        {
            maxAdViewers = adViewers;
            answerSec = sec - advLen + 1;
        }
    }

성능 평가

sliding window 알고리즘의 시간 복잡도는 전체 동영상 재생시간에 선형적으로 증가하는 반면 totalViewers배열에 데이터를 삽입할 때는 이중 반복문이 등장합니다. 이중 반복문은 logs 배열의 크기(시청 기록의 수)와 각 배열에 있는 시작시간과 끝 시간의 차이(최대 크기: 동영상 재생시간) 만큼의 시간이 소요됨을 알 수 있습니다. 따라서 시청 기록의 개수를 \(n\), 동영상의 최대 길이를 \(l\)이라고 했을 때 시간 복잡도는 \(O(n\cdot l)\)인 알고리즘입니다. 공간 복잡도는 동영상 최대의 크기의 배열 totalViewers와 시청기록을 담는 logs 배열이 필요하기 때문에 \(O(n + l)\) 입니다.

전체 소스 코드

#include <string>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int StrToInt(const string& str)
{
    int h{}, m{}, s{};
    h = atoi(str.substr(0, 2).c_str());
    m = atoi(str.substr(3, 2).c_str());
    s = atoi(str.substr(6, 2).c_str());

    return (h * 3600) + (m * 60) + s;
}
string IntToStr(int sec)
{
    int h, m, s;
    h = sec / 3'600;
    sec -= h * 3'600;
    m = sec / 60;
    sec -= m * 60;
    s = sec;

    string hh, mm, ss;
    if (h < 10) hh + "0";
    hh + to_string(h);

    if (m < 10) mm + "0";
    mm + to_string(m);

    if (s < 10) ss + "0";
    ss + to_string(s);

    return hh + ":" + mm + ":" + ss;
}

string solution(string play_time, string adv_time, vector<string> logs) {
    string answer = "";

    // 동영상 길이
    int playLen = StrToInt(play_time);

    // 광고 길이
    int advLen = StrToInt(adv_time);

    // totalViewers[sec]: sec 초에 영상을 시청중인 사람 수,
    // size: 전체 동영상 길이 + 1
    // 초기값: 모든 원소 0으로 초기화
    vector<int> totalViewers(playLen + 1, 0);

    // totalViewers 배열에 시청기록 입력
    for (string log : logs)
    {
        int start = StrToInt(log.substr(0, 8));
        int end = StrToInt(log.substr(9, 8));
        // log의 시청 시작 시간 부터 시청 종료시간 까지 시청자 수 ++
        for (int sec = start; sec < end; sec++)
            totalViewers[sec]++;
    }

    // 큐를 이용한 sliding window 알고리즘
    queue<int> q;

    long long adViewers{}; // 현재 구간 광고 시청자수  
    long long maxAdViewers{}; // 광고 시청자수가 최대인 구간의 시청자 수
    int answerSec{};          // 광고 시청자수가 최대인 구간 시작점

    for (int sec = 0; sec < advLen; sec++)
    {
        adViewers += totalViewers[sec];
        q.push(totalViewers[sec]);
    }

    maxAdViewers = adViewers;
    answerSec = 0;

    for (int sec = advLen; sec < playLen; sec++)
    {
        adViewers += totalViewers[sec];
        q.push(totalViewers[sec]);

        adViewers -= q.front();
        q.pop();

        if (maxAdViewers < adViewers)
        {
            maxAdViewers = adViewers;
            answerSec = sec - advLen + 1;
        }
    }

    answer = IntToStr(answerSec);
    return answer;
}