[구간합] 광고 삽입 - 2021 KAKAO BLIND RECRUITMENT

해결 방법

필자는 초 단위로 누적 재생시간에 대한 구간합을 구해서 해결했다. 최대 재생 시간은 359999초이기 때문에 O(N)의 시간복잡도 정도는 부담스럽지 않다. 이렇게 구간합을 구해두면 [0, adv_time) 구간부터 [play_time - adv_time, play_time)에 대한 모든 구간합을 구하는데 O(N)의 시간복잡도로 해결할 수 있다.

그리고 "hh:mm:ss" 문자열 형식으로 표현된 시간을 초 단위의 정수로 변환하는 함수와 초 단위의 정수를 "hh:mm:ss" 문자열 형식으로 변환하는 함수를 추가해서 손 쉽게 시간을 계산할 수 있도록 했다.

 

 

소스 코드

#include <string>
#include <vector>
using namespace std;

#define MAX 360000

int dup[MAX]; // 시간별 재생 수
long long acc_dup[MAX]; // 시간별 누적합

// "hh:mm:ss"를 초 단위 정수로 변환
int convert_to_int(string str) {
    int h = stoi(str.substr(0, 2));
    int m = stoi(str.substr(3, 2));
    int s = stoi(str.substr(6, 2));
    return 3600*h+60*m+s;
}

// 초 단위 정수를 "hh:mm:ss"로 변환
string convert_to_string(int i) {
    string str="";
    int h = i/3600;
    if(h<10) str+="0";
    str+=to_string(h)+":";
    i-=(h*3600);
    int m = i/60;
    if(m<10) str+="0";
    str+=to_string(m)+":";
    i-=(m*60);
    if(i<10) str+="0";
    str+=to_string(i);
    return str;
}

string solution(string play_time, string adv_time, vector<string> logs) {
    string answer = "";
    int pti=convert_to_int(play_time);
    int ati=convert_to_int(adv_time);
    for(int i=0;i<logs.size();i++) {
        int start = convert_to_int(logs[i].substr(0, 8));
        int end = convert_to_int(logs[i].substr(9, 8));
        dup[start]++;
        dup[end]--;
    }
    
    // 시간별 재생수와 누적합 구하기
    acc_dup[0]=dup[0];
    for(int i=1;i<MAX;i++) {
        dup[i]+=dup[i-1];
        acc_dup[i]=acc_dup[i-1]+dup[i];
    }
    
    // 최대 구간합과 시작 시간 구하기
    long long maxi=0;
    int answeri=0;
    for(int i=ati;i<pti;i++) {
        if(acc_dup[i]-acc_dup[i-ati]>maxi) {
            maxi=acc_dup[i]-acc_dup[i-ati];
            answeri=i-ati;
        }
    }
    
    if(answeri==0) return "00:00:00";
    answer=convert_to_string(answeri+1); // 구간의 오른쪽 끝부분은 재생되지 않았다고 가정하기 때문에 시작 시간의 -1로 계산되며, 이에 따른 보정이 필요함
    return answer;
}

 

테스트케이스 31개 모두 정답

 

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