[1일 1알고] 광고 삽입

https://school.programmers.co.kr/learn/courses/30/lessons/72414

프로그래머스

이번 문제는 구현 문제입니다.

 

전체 영상 중 광고를 어느 타이밍에 틀지가 문제입니다.

 

일단 가장 많은 사람이 시청하도록 해야하기 때문에 어느 특정 시점부터 광고를 트는 시간 동안 사람들이 누적 몇초를 시청했는지를 알아야합니다.

 

그렇다면 동영상 재생시간 동안 매초 몇명이 시청중인지를 계산해야합니다.

다만 매번 계산할 수는 없기 때문에 슬라이딩 윈도우 형식으로 계산하면 될 것 같습니다.

 

그리고 매초 몇명이 보고있는지를 확인하기 위해서는 주어진 logs를 통해서 미리 배열에 누적시켜놓아야할 것입니다.

기본적으로 시간은 최대 100시간이기 때문에 초단위로 계산한다면 순회를 할 때 최대 100 * 60 * 60 = 36만 번의 계산이 필요한데, logs가 최대 30만개 이기 때문에 logs마다 매초 하나하나 누적시키면 터질 것입니다.

 

따라서 시작 시간과 끝나는 시간을 통해 누적합으로 만드는 것이 타당해 보입니다.

---

using namespace std;
// 최대한 많은 사람이 볼 수 있도록 광고 삽입
// 누적 재생 시간이 가장 많이 나오는 곳
// 답이 여러개라면 가장 빠른 시각

// play_time = 전체 동영상 길이
// adv_time = 광고 길이
// logs = 시청자의 재생 기록

struct Time
{
    int h, m, s;
};

void ParsingTime(Time& time, string str)
{
    time.h = (str[0] - '0') * 10 + (str[1] - '0');
    time.m = (str[3] - '0') * 10 + (str[4] - '0');
    time.s = (str[6] - '0') * 10 + (str[7] - '0');
}

void ParsingLog(Time& startTime, Time& endTime, string str)
{
    startTime.h = (str[0] - '0') * 10 + (str[1] - '0');
    startTime.m = (str[3] - '0') * 10 + (str[4] - '0');
    startTime.s = (str[6] - '0') * 10 + (str[7] - '0');

    endTime.h = (str[9] - '0') * 10 + (str[10] - '0');
    endTime.m = (str[12] - '0') * 10 + (str[13] - '0');
    endTime.s = (str[15] - '0') * 10 + (str[16] - '0');
}

int GetSec(Time& time)
{
    return time.h * 60 * 60 + time.m * 60 + time.s;
}

void ParsingTimeReverse(string& time_str, int sec)
{
    int h = sec / 3600;
    sec -= h * 3600;
    int m = sec / 60;
    sec -= m * 60;
    int s = sec;

    time_str += h / 10 + '0';
    time_str += h % 10 + '0';
    time_str += ":";
    time_str += m / 10 + '0';
    time_str += m % 10 + '0';
    time_str += ":";
    time_str += s / 10 + '0';
    time_str += s % 10 + '0';
}
string solution(string play_time, string adv_time, vector<string> logs) {
    string answer = "";

    Time total_time;
    ParsingTime(total_time, play_time);

    int N = GetSec(total_time);

    vector<int> users_cnt_temp(N+1, 0);
    vector<int> users_cnt(N+1, 0);

    for (int i = 0; i < logs.size(); ++i)
    {
        Time startTime, endTime;
        ParsingLog(startTime, endTime, logs[i]);
        ++users_cnt_temp[GetSec(startTime)];
        --users_cnt_temp[GetSec(endTime)];
    }

    users_cnt[0]  = users_cnt_temp[0];

    for (int i = 1; i <= N; ++i)
    {
        users_cnt[i] = users_cnt[i - 1] + users_cnt_temp[i];
    }

    Time t_adv_time;
    ParsingTime(t_adv_time, adv_time);
    int i_adv_sec = GetSec(t_adv_time);

    long long curSum = 0;

    for (int i = 0; i < i_adv_sec; ++i)
    {
        curSum += users_cnt[i];
    }

    long long maxSum = curSum;
    int answerTime = 0;

    for (int start = 1; start <= N - i_adv_sec; ++start)
    {
        curSum -= users_cnt[start - 1];
        curSum += users_cnt[start + i_adv_sec - 1];

        if (curSum > maxSum)
        {
            maxSum = curSum;
            answerTime = start;
        }
    }

    ParsingTimeReverse(answer, answerTime);
    return answer;
}

 

시간이 기본적으로 string으로 주어지고 정답도 string이기 때문에 간단하게 파싱도 필요합니다.