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

프로그래머스 광고 삽입 [2021 KAKAO BLIND RECRUITMENT]
https://programmers.co.kr/learn/courses/30/lessons/72414

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

문제 풀이

• 이 문제는 Sliding Window 알고리즘을 사용해 해결했습니다.
• 공익광고 재생시간 크기의 윈도우를 동영상 재생시간의 처음부터 끝까지 슬라이딩하면서 윈도우 내 값의 총 합이 제일 큰 경우(시청자들의 누적 재생시간이 가장 많은 곳)를 리턴합니다. 
• 시청자들의 누적 재생시간을 표시하기 위해 누적합의 개념을 사용했습니다. (반복문을 사용해도 테스트 통과합니다!)

코드

#include <string>
#include <vector>

using namespace std;

int arr[360010]; // 3600 * 99 + 60 * 59 + 59 -> 최대 재생 시간

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

string time_tostring(int t) {
    string ret = "";
    
    int h = t / 3600; t %= 3600;
    int m = t / 60;
    int s = t % 60;
    
    ret += h >= 10 ? to_string(h) : ("0" + to_string(h));
    ret += ":";
    ret += m >= 10 ? to_string(m) : ("0" + to_string(m));
    ret += ":";
    ret += s >= 10 ? to_string(s) : ("0" + to_string(s));
    
    return ret;
}

string solution(string play_time, string adv_time, vector<string> logs) {
    int END = time_to_sec(play_time);
    int ADV = time_to_sec(adv_time);
    
    int answer = 0;
    long long sum = 0;
    
    for(string log: logs) {
        int t1 = time_to_sec(log.substr(0, 8));
        int t2 = time_to_sec(log.substr(9));
        
        // 누적합
        arr[t1] += 1;
        arr[t2] -= 1;
        
        /*
        - 반복문 사용시
        for(int i=t1; i<t2; ++i) arr[i]++;
        */
    }
    // 누적합 계산
    for(int i=0; i<END-1; ++i) arr[i+1] += arr[i];
    
    // 공익광고 재생시간 윈도우 
    for(int i=0; i<ADV; ++i) sum += arr[i];

    long long max_sum = sum;
    for(int i=ADV; i<END; ++i) {
    	// 한 칸씩 슬라이딩하면서 sum 계산
        sum -= arr[i-ADV];
        sum += arr[i];
        
        if(sum > max_sum) {
            max_sum = sum;
            answer = i - ADV + 1;
        }
    }
    
    return time_tostring(answer);
}

실행 결과