[프로그래머스][level3] 광고 삽입 (C++)

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

[난이도] level3
[유형] 부분합

[풀이]
시간의 최대 길이가 N:100*60*60 정도에 logs의 크기가 M:300000 이므로
O(N*M) 알고리즘으로는 시간내에 해결이 불가능 합니다.
O(N) 혹은 O(M) 알고리즘을 생각해봐야 합니다.
NlogN을 생각하려면 정렬, 이분탐색 , set 등과 연관이 있어야 하는데 연관도가 떨어져 보입니다.

cnt[i] = 0~i까지 재생했을 때 총 누적 재생시간 (0<= i <= 나올 수 있는 최대 시간) 을 저장하는
cnt 배열을 만듦으로써 O(N+M)의 답을 구할 수 있습니다.

1)
일단 logs의 string을 초로 변환하여 start,end 타임을 구합니다.
sscanf(str.c_str(),"%d:%d:%d",&h,&m,&s) 와 같이 sscanf를 쓰면
형식이 정해진 string에서 필요한 정보를 쉽게 추출할 수 있습니다.

2)
구한 start,end를 이용해 cnt[start+1]++, cnt[end+1]-- 연산을 해주어
start와 end 지점에서 한 시청자의 재생이 시작,종료 되었음을 기록합니다.
+1을 해주는 이유는 start에서 재생이 시작 되었다면 start+1이 되서야 1초가 경과한 것이기 때문입니다.
마찬가지로 end일때도 end에 종료되면 end+1부터 종료가 된것이 영향이 있기 때문입니다.

3)
cnt[i]를 이용해 cnt[i]를 i초에 몇명의 시청자가 재생중인지를 기록하도록 할 것입니다.
for(int i=1;i<=pt;i++) cnt[i]+=cnt[i-1] 와 같이 누적합을 구해주면 됩니다.

4)
한번 더 위와 3)과 같이 누적해주면 cnt[i] = 0~i까지 재생했을 때 총 누적 재생시간 이 됩니다.
0~i까지 누적해서 더하기 때문에 위의 결과가 저장되는 것입니다.

5)
이제 어느 구간이 가장 누적 재생시간이 많이 나오는 지를 구해야 합니다.
cnt[i]-cnt[i-at] (at:adv_time <= i <= pt:play_time) 중 최댓값을 구하면서 그때의 i-at (시작 시간)을 구해줍니다.
이 값을 HH:MM:SS 형식으로 변환해주면 됩니다.

 

#include <string>
#include <vector>
using namespace std;
using ll = long long;
int pt,at;
ll cnt[400000];
int convert(string str){
    int h,m,s;
    sscanf(str.c_str(),"%d:%d:%d",&h,&m,&s);
    return h*3600+m*60+s;
}
string solution(string play_time, string adv_time, vector<string> logs) {

    pt=convert(play_time);
    at=convert(adv_time);

    vector<pair<int,int>> v;
    for(auto s : logs){
        int idx=s.find("-");
        int start=convert(s.substr(0,idx)), end=convert(s.substr(idx+1));
        cnt[start+1]++;
        cnt[end+1]--;
    }
    for(int j=0;j<2;j++)
        for(int i=1;i<=pt;i++) 
            cnt[i]+=cnt[i-1];

    ll mv=0;
    int t=0;
    for(int i=at;i<=pt;i++){
        if(mv<cnt[i]-cnt[i-at]){
            mv = cnt[i]-cnt[i-at];
            t=i-at;
        }
    }
    string rh=to_string(t/3600); 
    string rm=to_string((t%3600)/60);
    string rs=to_string((t%60));
    if(rh.size()<2) rh='0'+rh;
    if(rm.size()<2) rm='0'+rm;
    if(rs.size()<2) rs='0'+rs;
    string ret = rh+":"+rm+":"+rs;
    return ret;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level3/광고_삽입.cpp