프로그래머스 - 광고 삽입

프로그래머스 - 광고 삽입

윈도우 문제이다.

특정 구간의 합이 최대가 되는 구간을 찾으면 되는데, 평범하게 찾는다면 O(NM)만에 찾을 수 있다. (M = 찾으려는 구간의 길이)

이를 윈도우 알고리즘으로 개선하면, 0~M까지의 합을 구해놓고, M+1~N까지 진행하면서 0~M까지의 합에서 0을 빼고, M+1을 더하면 1~M+1까지의 합이 된다. 이를 반복하면서 최대값을 갱신해주면 된다.

구간합을 구할 때는 Long Long을 사용해야 한다. (int는 넘어가서 제출하면 몇개는 틀린다고 나온다)

코드는 다음과 같다.

#include <string>
#include <vector>

using namespace std;

#define ll long long

const inline int parse_time(string log)
{
    int h = stoi(log.substr(0, 2)) * 3600;
    int m = stoi(log.substr(3, 2)) * 60;
    int s = stoi(log.substr(6, 2));
    
    return h + m + s;
}

string int_to_str(int t)
{
    int h = t / 3600;
    int m = (t % 3600) / 60;
    int s = (t % 3600) % 60;
    string hour_str = to_string(h); 
    hour_str = h < 10 ? "0" + hour_str : hour_str;
    string min_str = to_string(m); 
    min_str = m < 10 ? "0" + min_str : min_str;
    string sec_str = to_string(s); 
    sec_str = s < 10 ? "0" + sec_str : sec_str;
    
    return hour_str + ":" + min_str + ":" + sec_str;
}

string solution(string play_time, string adv_time, vector<string> logs) {
    string answer = "00:00:00";
    if(play_time == adv_time)
        return answer;
    
    int time = parse_time(play_time);
    vector<int> acc_vec(time, 0);
    
    for(int i=0;i<logs.size();i++) {
        int start_time = parse_time(logs[i].substr(0, 8));
        int finish_time = parse_time(logs[i].substr(9, 17));
        for(int j=start_time;j<finish_time;j++) 
            acc_vec[j]++;
    }
    
    int adv_len = parse_time(adv_time);
    ll acc = 0, max_acc;
    for(int i=0;i<adv_len;i++) 
        acc += acc_vec[i];
    max_acc = acc;
    
    int idx = 0, result_idx = 0;
    for(int i=adv_len;i<time;i++) {
        acc = acc - acc_vec[idx] + acc_vec[i];
        if(acc > max_acc) {
            max_acc = acc;
            result_idx = idx + 1;
        }
        idx++;
    }
    answer = int_to_str(result_idx);
    return answer;
}