[프로그래머스] 광고 삽입

문제 링크 : programmers.co.kr/learn/courses/30/lessons/72414

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

문제 유형

Lazy Propagation

 

※ 이 풀이에서는 공식 해답과 다르게 Lazy Propagation을 사용하였다. 공식 해답의 풀이는 추후 추가 예정

세그먼트 트리(Segment Tree) : Lazy Propagation

2021 카카오 블라인드 테스트의 5번 문제이다.

최대 시간이 99:59:59 이므로, 초를 기준으로 0 ~ 360,000 초의 시간 범위를 갖는다. 

각 재생 구간의 시작과 끝에 해당하는 범위에 대해 +1 update 하고,

0초부터 광고가 삽입될 수 있는 최대 위치까지의 모든 시작점을 기준으로 query의 최댓값을 구해주면 된다.

단, 1~3초 동안 재생되는 동영상의 길이가 2라는 것에 주의하자. 구간을 1, 2, 3초 각각의 점으로 생각한다면 이는 3개의 리프 노드를 갖지만, 실제로는 1~2, 2~3 의 구간으로써 두 리프 노드만 가진다.

(85번째 줄과 같이 end만 +1을 하지 않은 것으로 보정한다.)

 

[코드]

#include <string>
#include <vector>
#include <algorithm>
 
#define MAXSIZE 360010
 
using namespace std;
typedef long long ll;
 
ll segtree[MAXSIZE * 4];
ll lazy[MAXSIZE * 4];
 
void update_lazy(int node, int start, int end){
    if(lazy[node] != 0){
        segtree[node] += lazy[node] * ((ll)end - start + 1);
        if(start != end){
            lazy[node * 2] += lazy[node];
            lazy[node * 2 + 1] += lazy[node];
        }
        lazy[node] = 0;
    }
}
 
void update_range(int node, int start, int end, int l, int r, int val){
    update_lazy(node, start, end);
    
    if(end < l || start > r) return;        //벗어난 범위
    
    //완전히 포함될 경우
    if(l <= start && end <= r){
        segtree[node] += val * ((ll)end - start + 1);
        if(start != end){
            lazy[node * 2] += (ll)val;
            lazy[node * 2 + 1] += (ll)val;
        }
        return;
    }
    
    int mid = (start + end) / 2;
    update_range(node * 2, start, mid, l, r, val);
    update_range(node * 2 + 1, mid + 1, end, l, r, val);
    segtree[node] = segtree[node * 2] + segtree[node * 2 + 1];
}
 
ll query(int node, int start, int end, int l, int r){
    update_lazy(node, start, end);
    
    if(l > end || start > r) return 0;
    
    if(l <= start && end <= r) return segtree[node];
    
    int mid = (start + end) / 2;
    return query(node * 2, start, mid, l, r) + query(node * 2 + 1, mid + 1, end, l, r);
}
 
int trans_val(string timeval){
    int h = atoi(timeval.substr(0, 2).c_str());
    int m = atoi(timeval.substr(3, 2).c_str());
    int s = atoi(timeval.substr(6, 2).c_str());
    return h * 3600 + m * 60 + s;
}
 
string trans_str(int timeval){
    int h = timeval / 3600; timeval %= 3600;
    int m = timeval / 60; timeval %= 60;
    int s = timeval;
    
    string hs = h < 10 ? "0" + to_string(h) : to_string(h);
    string ms = m < 10 ? "0" + to_string(m) : to_string(m);
    string ss = s < 10 ? "0" + to_string(s) : to_string(s);
    
    return hs + ":" + ms + ":" + ss;
}
 
string solution(string play_time, string adv_time, vector<string> logs) {
    string answer = "";
    
    ll maxtime = trans_val(play_time) + 1;
    ll adtime = trans_val(adv_time);
    ll maxval = 0, startpos = 0;
    
    for(int i = 0; i < logs.size(); i++){
        int start = trans_val(logs[i].substr(0, 8));
        int end = trans_val(logs[i].substr(9));
        update_range(1, 1, MAXSIZE, start + 1, end, 1);
    }
    
    for(int i = 1; i < maxtime; i++){
        int end = i + adtime;
        if(end > maxtime) break;
        ll res = query(1, 1, MAXSIZE, i, end - 1);
        if(res > maxval){
            maxval = res;
            startpos = i - 1;
        }
    }
    
    answer = trans_str(startpos);
    
    return answer;
}