광고 삽입 [Lv. 3]

프로그래머스

동영상 길이, 시청된 동영상 구간, 광고 길이를 입력받을 때

어느 위치에 광고를 넣어야 효율을 최대화 할 수 있는지 찾는 문제입니다.

 

풀이 방법

모든 동영상 구간의 합을 효율적으로 구해서 최대치를 찾고 출력하면 해결되는 문제입니다.

00:00:00 부터 최대 99:59:59까지 ( 360,000 크기의 배열 ) 탐색해야하기 때문에

문제 해결을 위해서는 최적화가 필수적입니다.

시청 기록을 의미하는 logs 배열의 크기가 최대 30만이며 모든 시청 시간이 00:00:00 ~ 99:59:59 일 수 있기에

이 모든 것을 하나하나 탐색하면 절대 문제를 풀 수 없습니다.

 

이때 필요한 것이 누적합을 효율적으로 구하는 알고리즘입니다.

long dp[360000];

for (string l : logs)
{
    vector<string> log = split(l);
    int start = ttoi(log[0]); // time을 int로 변환하는 함수
    int end = ttoi(log[1]);
    dp[start]++;
    dp[end]--;
}

int v_size = ttoi(play_time);
    
for (int i = 1; i < v_size; i++)
    dp[i] += dp[i - 1];

 

모든 시청 기록의 시작 지점과 끝 지점에 ++, --로 체크만 해두고

누적해서 더해 나가면 해당 시간대의 시청시간을 빠르게 저장할 수 있습니다.

 

또한 광고 길이 만큼 구간의 합을 찾아서 비교해야 하는데

이 부분에서도 광고 길이만큼 탐색하면 시간이 많이 소모됩니다.

long sum = 0;    
for (int i = 0; i < a_size; i++)
    sum += dp[i];
        
int answer = 0;
long max_sum = sum;
for (int i = a_size; i < v_size; i++)
{
    sum -= dp[i - a_size];
    sum += dp[i];

    if (max_sum < sum)
    {
        answer = i - a_size + 1;
        max_sum = sum;
    }
}

구간에서 벗어난 기록은 지우고 구간에 새로 추가된 기록은 합하는 방식으로

N의 속도로 해결했습니다.

 

정답 코드

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int ttoi(string time)
{
    int ret = 0;

    ret += time[7] - '0';      // 1초
    ret += (time[6] - '0')* 10; // 10초
    
    ret += (time[4] - '0') * 60; // 1분
    ret += (time[3] - '0') * 600; // 10분
    
    ret += (time[1] - '0') * 3600; // 1시간
    ret += (time[0]- '0') * 36000; // 10시간
    
    return ret;
}

string itot(int time)
{
    string ret;
    
    ret += to_string(time / 36000);
    time %= 36000;
    
    ret += to_string(time / 3600);
    time %= 3600;
    
    ret += ":";
    
    ret += to_string(time / 600);
    time %= 600;
    
    ret += to_string(time / 60);
    time %= 60;
    
    ret += ":";
    
    ret += to_string(time / 10);
    time %= 10;
    
    ret += to_string(time);
    
    return ret;   
}

vector<string> split(string str)
{
    vector<string> ret;
    string s;
    for (auto c : str)
    {   
        if (c == '-')
        {
            ret.push_back(s);
            s = "";
            continue;
        }
        s += c;
    }
    ret.push_back(s);
    return ret;
}

long dp[360000];
string solution(string play_time, string adv_time, vector<string> logs) {  
    for (string l : logs)
    {
        vector<string> log = split(l);
        int start = ttoi(log[0]);
        int end = ttoi(log[1]);
        dp[start]++;
        dp[end]--;
    }
  
    int v_size = ttoi(play_time);
    int a_size = ttoi(adv_time);
    
    for (int i = 1; i < v_size; i++)
        dp[i] += dp[i - 1];
    
    long sum = 0;    
    for (int i = 0; i < a_size; i++)
        sum += dp[i];
    
    int answer = 0;
    long max_sum = sum;
    for (int i = a_size; i < v_size; i++)
    {
        sum -= dp[i - a_size];
        sum += dp[i];
        
        if (max_sum < sum)
        {
            answer = i - a_size + 1;
            max_sum = sum;
        }
    }
    
    
    return itot(answer);
}