2021 KAKAO Blind - 5. 광고 삽입

목차

1. 개요
2. 설명
3. 코드

 

개요

시청자가 어떠한 패턴으로 영상을 감상하는지 정보가 주어질 때, 어느 구간에서 가장 좋은 광고 효과를 낼 수 있는지 찾아내는 문제입니다.

 

이 문제의 Key point는 00:00:00 ~ 99:59:59 의 시간을 하나의 배열 (0 ~ 359999)로 표현하고, $O(N)$의 복잡도로 결과를 찾아내는 것입니다.

 

사용자의 play time이 주어지면 0 부터 359999 사이의 값으로 환산 한 뒤, 각 배열 원소 (1초)마다 총 몇 명이 시청하는지 저장합니다.

 

이후, 광고 삽입 시간을 0부터 359999까지 차례로 조사하면서 총 시청 인원이 가장 많은 구간을 구하면 되겠습니다.

 

설명

다음과 같이 간단한 예제와 그림을 통해서 살펴보도록 하겠습니다.

재생 가능한 시간 0 : 00 ~ 0 : 20 (배열 원소 : 20개)

시청자 1의 재생 시간 0 : 10 ~ 0 : 15

시청자 2의 재생 시간 0 : 05 ~ 0 : 15

시청자 3의 재생 시간 0 : 12 ~ 0 : 18

광고 시간 : 4초

 

이를 수직선으로 나타내보면 다음과 같이 표현할 수 있습니다.

 

이제 위 수직선을 배열로 표현해서 각 1초 당 몇 명의 시청자가 동시에 존재하는지 나타내보면 됩니다! 여기서 종료 시간은 플레이 타임으로 치지 않는다는 것을 주의 해야합니다.

 

먼저 현재 시간에 시청 중인 인원 수를 저장할 변수 count를 생성합니다. 위 수직선을 시작 시간 순서대로 정렬한 뒤, 0초부터 차례로 시작해서 새로운 시청자가 들어오는 시간에 count + 1을, 나가는 순간에 count - 1을 합니다. 그리고 그 매 초마다 배열에 저장하면 됩니다. (arr[time] = count)

 

그렇다면 다음과 같은 배열을 얻을 수 있습니다.

 

 

이제 count의 부분합이 가장 많은 구간을 찾으면 됩니다! 이는 two pointer를 활용해 배열의 index를 하나씩 옮겨보면서 검사하면 쉽게 찾을 수 있습니다.

 

광고 시간이 4초이므로 앞에서부터 0 ~ 3, 1 ~ 4, 2 ~ 5, .... , 16 ~ 19 를 차례로 모두 검사해보면 됩니다. 시간복잡도는 $O(N)$ 이 되겠죠?!

 

위의 예제에서 부분합이 가장 큰 부분은 11 ~ 14입니다. 따라서 11초에 광고를 삽입해서 4초간 재생하는게 가장 효과가 크겠네요.

 

코드

※주의할 점

이 문제에서 시간을 다루지만, 이를 배열 하나에 담을 수 있는지 꼼꼼이 생각 해봐야겠습니다.

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

using namespace std;

int str2int(string a){
    int hour = (a[0]-'0')*10 + a[1]-'0';
    int min = (a[3]-'0')*10 + a[4]-'0';
    int sec = (a[6]-'0')*10 + a[7]-'0';
    return hour*3600+min*60+sec;
}
class Time{
    public:
    int time;
    bool start;
    Time(int time_, bool start_):time(time_), start(start_){};
    bool operator<(const Time& b){
        return time < b.time;
    }
};

vector<Time> t;
int arr[360001];
string solution(string play_time, string adv_time, vector<string> logs) {
    string answer = "";
    int ptime = str2int(play_time);
    int atime = str2int(adv_time);

    for(auto itr = logs.begin(); itr != logs.end(); itr++){
        t.push_back(Time(str2int(itr->substr(0,8)), true));
        t.push_back(Time(str2int(itr->substr(9,8)), false));
    }
    sort(t.begin(), t.end());
    int cnt = 0;
    auto next = t.begin();

    for(int i=0; i<ptime; i++){
        while(i == next->time){
            if(next->start) cnt++;
            else cnt--;
            next = next+1;
        }
        arr[i] = cnt;
    }

    int ans_time= 0, left=0, right=0;
    long maxval = 0, cumul = 0;
    for(right=0; right<atime; right++){
        cumul += arr[right];
    }
    maxval = cumul;
    while(right < ptime){
        cumul += arr[right] - arr[left];
        right++;
        left++;
        if(cumul > maxval){
           cumul = maxval;
            ans_time = left;
        }
    }
    int h = ans_time/3600;
    int m = (ans_time%3600)/60;
    int s = ans_time%60;

    if(h<10) answer = string("0");
    answer = answer + to_string(h) + string(":");
    if(m<10) answer = answer + string("0");
    answer = answer + to_string(m) + string(":");
    if(s<10) answer = answer + string("0");
    answer = answer + to_string(s);

    return answer;
}