프로그래머스 문제 - 광고 삽입

프로그래머스 광고 삽입 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

인기있는 동영상에 광고를 넣으려고 합니다.
한 동영상의 어떤 구간을 재생하는지 알 수 있는 재생구간 기록을 알 수 있으며, 해당 기록을 바탕으로 광고를 넣을 것입니다.
재생구간 내에서 광고를 같이 넣을 것이며, 최대한 재생시간이 많은 곳에 광고를 삽입해야 합니다.
최대한 재생시간이 많은 곳에 광고를 삽입한 시작 시간을 return해야 합니다.

문제 풀이

동영상 시간과 여러 재생구간, 광고 시간이 주어졌을 때 광고를 틀었을 때 누적 재생시간이 제일 큰 구간의 시작지점을 찾아야합니다.

구간들의 시작, 끝 부분을 기준으로 삼아 계산을 하는 코드를 작성해보았지만, 시간초과가 나오기 때문에 다른 방법을 사용해야 했습니다.
시,분,초로 나뉜 시간들은 초로만 시간을 표현할 수 있으니 이 시간대를 배열에 저장하여 구간을 찾는 방법을 사용하였습니다.

일단 긴 배열을 만든 후, 구간들을 전부 초로 변환하여 배열에 더해줍니다.

//시간을 초로 바꾼 후 구간을 배열 내에 더해줌
for(int i = 0; i < logs.size(); i++)
{
    Time t = Time(stoi(logs[i].substr(0, 2)) * 3600 + stoi(logs[i].substr(3, 2)) * 60 + stoi(logs[i].substr(6, 2)),
                  stoi(logs[i].substr(9, 2)) * 3600 + stoi(logs[i].substr(12, 2)) * 60 + stoi(logs[i].substr(15, 2)));
    for(int j = t.startTime; j < t.endTime; j++)
    {
        timeLog[j]++;
    }
}

이후 00:00:00초부터 시작하여 광고시간까지의 구간의 누적합을 구해준 후 1초씩 더하면서 광고시간만큼의 범위만큼 투포인터 알고리즘을 통해 누적합을 변경해주며 제일 큰 값을 찾아주면 됩니다.
이때 주의할 점은 재생이 시작된 구간은 누적합에 포함되며, 재생이 종료된 시각은 누적합의 값에 포함되면 안됩니다.

이후에 나온 값을 시,분,초로 변환하여 return시키면 됩니다.

전체 코드

#include <bits/stdc++.h>
#include <string>
#include <vector>

using namespace std;

struct Time{
    long long startTime;
    long long endTime;
        
    Time(long long a, long long b) : startTime(a), endTime(b)  {}
};

bool compare(Time a, Time b)
{
    return a.startTime < b.startTime;
}

string secondToTime(long long second)
{
    string str;
    int t = second / 3600;
    if(t < 10)
        str = "0" + to_string(t) + ":";
    else
        str = to_string(t) + ":";
    t = (second % 3600) / 60;
    if(t < 10)
        str += "0" + to_string(t) + ":";
    else
        str += to_string(t) + ":";
    t = (second % 3600) % 60;
    if(t < 10)
        str += "0" + to_string(t);
    else
        str += to_string(t);
    
    return str;
}

vector<int> timeLog(360000, 0);

string solution(string play_time, string adv_time, vector<string> logs) {
    string answer = "";
    
    long long answerSecond = 0;
    long long adTime = 0;
    long long playTime = 0;
    
    //시간을 초로 바꾼 후 구간을 배열 내에 더해줌
    for(int i = 0; i < logs.size(); i++)
    {
        Time t = Time(stoi(logs[i].substr(0, 2)) * 3600 + stoi(logs[i].substr(3, 2)) * 60 + stoi(logs[i].substr(6, 2)),
                           stoi(logs[i].substr(9, 2)) * 3600 + stoi(logs[i].substr(12, 2)) * 60 + stoi(logs[i].substr(15, 2)));
        for(int j = t.startTime; j < t.endTime; j++)
        {
            timeLog[j]++;
        }
    }
    
    //총 동영상 시간과 광고 시간도 초로 바꿔줌
    adTime = stoi(adv_time.substr(0, 2)) * 3600 + stoi(adv_time.substr(3, 2)) * 60 + stoi(adv_time.substr(6, 2));
    playTime = stoi(play_time.substr(0, 2)) * 3600 + stoi(play_time.substr(3, 2)) * 60 + stoi(play_time.substr(6, 2));
    
    //같다면 맨 처음 시간이 정답
    if(adTime == playTime)
    {
        return "00:00:00";
    }
    
    long long maxSum = 0;
    long long timeSum = 0;
    //맨 처음이 시작시간일 경우의 누적 재생시간
    for(int i = 0; i < adTime; i++)
    {
        timeSum += (long long)timeLog[i];
    }
    maxSum = timeSum;
    
    for(int i = adTime; i <= playTime; i++)
    {
        //시작시간을 1초씩 더하며 누적 재생시간의 값을 비교
        timeSum += (long long)(timeLog[i] - timeLog[i-adTime]);
        if(maxSum < timeSum)
        {
            maxSum = timeSum;
            answerSecond = i-adTime+1;
        }
    }
    //초로 되있는 값을 시간으로 변환
    answer = secondToTime(answerSecond);   
    
    return answer;
}

출저

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