프로그래머스 - 광고삽입

동영상 재생시간과  공익광고 재생 시간 범위가 00:00:01 이상  99:59:59 이하이므로

360000의 크기 안에서 시청자 재생시간의 시작 시각과 종료 시각을 카운트 해준다.

 

광고 재생시간의 left, right 포인터를 가지고 이동시키며, 위에서 카운트 해준 값을 이용해서 

left, right의 가중치 k, kk 를 빼고 더하며 시청자들의 누적 재생시간의 합을 계산해준다.

 

이때 시청자들의 누적 재생시간의 합이 최대 360000 * 300000 으로 int 범위를 넘어갈 수 있기때문에

long long 을 고려해주는 게 중요했다.

 

#include <string>
#include <vector>
#include <cstring>
#include <iostream>
using namespace std;
 
long long st[360005];
long long et[360005];
 
long long hmsTos(string s){
   long long ret = 0;
    ret += 3600 * stoi(s.substr(0,2));
    ret += 60 * stoi(s.substr(3,2));
    ret += stoi(s.substr(6,2));
    
    return ret;
}
 
string solution(string play_time, string adv_time, vector<string> logs) {
    string answer = "";
    
    memset(st, 0, sizeof(st));
    memset(et, 0, sizeof(et));
    
    long long pt = hmsTos(play_time);
    long long at = hmsTos(adv_time);
    long long mm = 0;
    
    for(int i=0; i<logs.size(); i++){
        st[hmsTos(logs[i].substr(0,8))]++;
        et[hmsTos(logs[i].substr(9,8))]++;
    }
    
    int l=0;
    int r=0;
    long long cur=0;
    long long ans=0;
    long long k=0;
    long long kk=0;
    
    
    while(r <= pt) {
        cur += (kk - k);
        if(cur>mm){
            mm = cur;
            ans = l;
        }
        
        kk += st[r];
        kk -= et[r];
        r++;
        
        if(r-l > at){
            k += st[l];
            k -= et[l];
            l++;
        }
    }
    
    long long hh = ans / 3600;
    ans -= 3600 * hh;
    if(hh<10) answer += "0";
    answer += to_string(hh);
    answer += ":";
    
    long long mmm = ans/60;
    ans -= 60 * mmm;
    if(mmm<10) answer += "0";
    answer += to_string(mmm);
    answer += ":";
        
    if(ans<10) answer += "0";
    answer += to_string(ans);
  
    
    return answer;
}