[프로그래머스] 광고삽입 (C++) (2021 KAKAO BLIND RECRUITMENT)

https://programmers.co.kr/learn/courses/30/lessons/72414?language=cpp 

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

이 문제에서는 효율성을 고려해야하는 문제로 구간합과 투포인터 알고리즘을 사용하였다. 

해당 알고리즘을 사용하기 전에 HH:MM:SS <-> 초로 바꿔주는 두가지 함수를 구현하였다. 

이후에는 구간합만 구하면 되는데, 이 부분이 핵심인 문제였다.

 

전체 구간 길이가 N이고 광고 길이가 M일때,  완전탐색으로 매번 i번째 부터 i+N까지 새로 구간합을 구해주면 O(M*N)의 시간복잡도로 효율성 테스트를 통과하지 못한다.

 

구간합의 길이가 N으로 고정되어 있다는 점을 생각하면 O(N)만에 문제를 해결할 수 있다.

 

해결 방법은 다음과 같다.

1. 0초부터 M까지의 구간합을 구해서 T라고 한다.

2. 1초부터 M+1까지의 구간합을 구해야하는데, 이때 맨처음부터 다시 구하는게 아닌 0초의 값을 빼고 M+1의 값을 더해준다. 맨 앞의 값을 빼고 맨 뒤에 값을 넣는다는 점에서 자료구조 큐를 사용한다.

3. 2번에서 구한 구간합이 현재까지 나온 최대 구간합보다 크면 해당 구간합으로 변경한다.

4. 2~3번을 반복한다.

(포인터를 양 끝에 2개를 유지한다는 점에서 투포인터 알고리즘이라고 말할 수 있다)

 

완전탐색 대신 투포인터 알고리즘을 사용하면 누적합을 효율적으로 구할수 있다는걸 알아두자.

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int cnt[360000];//00:00:00 ~ 99:59:59를 초로 계산하면 0~359999

int strtoint(string s) { //00:00:00 포맷 -> 초
    string sec = s.substr(6, 2);
    string min = s.substr(3, 2);
    string hour = s.substr(0, 2);

    int result = stoi(sec) + stoi(min) * 60 + stoi(hour) * 60 * 60;
    return result;
}

string inttostr(int i) { //초 -> 00:00:00 포맷
    int sec = i % 60;
    i /= 60;
    int min = i % 60;
    i /= 60;
    int hour = i;
    string result = "";
    if(hour<10)result+="0";
    result += to_string(hour);
    result += ":";
    if (min < 10)result += "0";
    result += to_string(min);
    result += ":";
    if (sec < 10)result += "0";
    result += to_string(sec);
    
    return result;
}


string solution(string play_time, string adv_time, vector<string> logs) {
    string answer = "";
    for (int i = 0; i < logs.size(); i++) { //각 재생시간에 해당하는 구간에 +1
        int start = strtoint(logs[i].substr(0, 8));
        int end = strtoint(logs[i].substr(9));
        for (int j = start; j < end; j++) {
            cnt[j]++;
        }
    }
    int playtime = strtoint(play_time); //총 재생시간
    int advtime = strtoint(adv_time); //광고시간

    queue<int> q; //가장 첫 원소를 빼고 뒤에 삽입하기 때문에 큐사용
    int index=0; //결정된 광고 시작시간
    long long tmp = 0; 
    long long result = 0; //최대 구간합

    for (int i = 0; i < advtime; i++) {//0초부터 시작했을때 구간합
        tmp += cnt[i];
        q.push(cnt[i]);
    }

    result = tmp;
    for (int i=advtime; i < playtime; i++) { //투 포인터 알고리즘 
        tmp-=q.front();
        q.pop();
        tmp += cnt[i];
        q.push(cnt[i]);
        if (result < tmp) {//구간합이 최대일때
            result = tmp;
            index = i - advtime + 1;//현재 광고 시작시간
        }
    }
    answer = inttostr(index);

    return answer;
}