Programmers - 광고삽입(C++)

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

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

풀이

완전 탐색의 경우 O(N(전체 구간 길이) x M(광고의 길이))

시간을 초단위로 1초씩 이동 -> 구간의 합을 계산 O(N)으로 계산

1. logs에 대해 초로 변환, 시작 - 끝 값에 대해 재생 사람수 카운트

2. 0~(동영상 길이-광고 길이)에 대해 한 칸씩 슬라이딩을 옮기며 최대값 비교 

3. 최댓값에 대한 시작 초를 시간 문자열로 변환

#include <string>
#include <vector>

#define MAXLEN 360000//99:59:59
using namespace std;

int video_time[MAXLEN];

string sec_to_time(int sec){//sec->시간(h:m:s) 
    string time="";
    
    int hour=sec/3600;
    sec%=3600;
    int min=sec/60;
    sec%=60;
    if(hour<10)
        time+="0";
    time+=to_string(hour)+":";
    if(min<10)
        time+="0";
    time+=to_string(min)+":";
    if(sec<10)
        time+="0";
    time+=to_string(sec);
    
    return time;
}
int time_to_sec(string time){//시간(h:m:s) -> sec
    int hour=stoi(time.substr(0,2));
    int min=stoi(time.substr(3,5));
    int sec=stoi(time.substr(6,8));
    sec+=hour*60*60+min*60;
    return sec;
}
string solution(string play_time, string adv_time, vector<string> logs) {
    string answer = "";
    
    //logs의 시작/끝 시간 변환, 구간 합 갱신
    for(int i=0;i<logs.size();i++){
        int start=time_to_sec(logs[i].substr(0,8));
        int end=time_to_sec(logs[i].substr(9,17));
        for(int j=start;j<end;j++){
            video_time[j]++;
        }
    }
    
    int adv_len=time_to_sec(adv_time);
    int video_len=time_to_sec(play_time);
    
    long long max_sum=0;
    long long sum=0;
    int Start_time=0;
    for(int i=0;i<adv_len;i++){//0~광고 길이 
        sum+=video_time[i];
    }
    max_sum=sum;
    
    //start_time~start_time+광고길이-1 대해 광고 시청수의 최댓값 비교
    for(int start_time=1; start_time<=(video_len-adv_len+1); start_time++){
        sum+=video_time[start_time+adv_len-1];
        sum-=video_time[start_time-1];
        if(sum>max_sum){
            sum=max_sum;
            Start_time=start_time;
        }
    }
    
    return sec_to_time(Start_time);
}