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

 

해당 문제는 2021 KAKAO BLIND RECRUITMENT 출제 문제로 공식 해설이 있습니다.

2021 카카오 신입공채 1차 온라인 코딩 테스트 for Tech developers 문제해설

 

해설

1) 가장 많은 줄이 겹치는 지점이나 구간을 구할 때 떠올리면 좋은 스킬이 있다.

바로, 모든 로그의 시작점과 끝점에 대하여 (시작, +1), (끝, -1)을 저장한 배열을 만들고 해당 배열을 정렬하여 특정 포인트에 몇개의 +1과 -1이 추가 되는지 검사하는 것이다. 시간 t 지점에 겹치는 재생 목록이 n개인데 새로 시작되는 재생목록이 plus개, 끝나는 재생목록이 minus개라면 t+1 지점에는 겹치는 재생목록이 n+plus-minus 개가 된다.

 

log 배열을 이용하여 시간 t에 도달했을 때 추가되는 재생목록의 개수(재생시간의 합)을 rec[t]에 저장하자.

 

2) 각 시간에서 추가되는 재생목록의 수를 구해놓았다면, 슬라이딩 윈도우 기법을 이용해 크기가 adv_time(at)인 구간의 최대 합을 구하면 된다. 먼저, (0, at]까지의 재생시간 합(sum)을 구해놓자. 구간을 오른쪽으로 이동시킬 때는, en을 오른쪽으로 이동함과 동시에 rec[en]을 추가한다. st도 오른쪽으로 이동시키고 rec[st]를 제거한다. 

 

각 구간에서 도출된 sum 값 중에서 최댓값을 저장하여 리턴하면 정답이다.

 

 

주의 할 점

sum 값이 int 범위를 초과할 수 있으므로 자료형 long long을 사용해야 한다.

 

 

코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
using ll = long long;

#define X first
#define Y second

ll mx;
int pt, at, ans;
int h1, m1, s1, h2, m2, s2;

vector<ii> vlog;
vector<int> rec(400000, 0);

int tosec(int h, int m, int s) {
    return h*3600+m*60+s;
}

string tostr(int sec) {

    char tmp[50];
    int l = sprintf(tmp, "%02d:%02d:%02d", sec/3600, sec%3600/60, sec%3600%60);
    return string(tmp, l);
}

void setConditions(const string& play_time, const string& adv_time, const vector<string>& logs) {

    sscanf(play_time.c_str(), "%d:%d:%d", &h1, &m1, &s1);
    pt = tosec(h1, m1, s1);

    sscanf(adv_time.c_str(), "%d:%d:%d", &h1, &m1, &s1);
    at = tosec(h1, m1, s1);

    for (auto x : logs) {
        sscanf(x.c_str(), "%d:%d:%d-%d:%d:%d", &h1, &m1, &s1, &h2, &m2, &s2);
        int st = tosec(h1, m1, s1);
        int en = tosec(h2, m2, s2);
        vlog.push_back({st, +1});
        vlog.push_back({en, -1});
    }
    sort(vlog.begin(), vlog.end());
}

//각 시간대를 포함할 때 누적되는 재생시간을 구해 rec[t]에 저장
void setRec() {

    int t = 0, idx = 0, cnt = 0;
    while (t <= pt) {
        int plus = 0, minus = 0;
        while (idx < (int)vlog.size() && vlog[idx].X == t) {
            if (vlog[idx].Y == +1) plus++;
            else minus++;
            idx++;
        }
        rec[t] = cnt;
        cnt += (plus-minus);
        t++;
    }
}

//슬라이딩 윈도우로 크기가 at인 구간의 최대 합 구하기
void findStart() {

    ll sum = 0;
    int st = 0, en = 1;

    //(0, at]까지의 합
    while (en <= at) sum += rec[en++];
    en--;
    mx = sum;

    //st와 en을 한칸씩 이동하여 합 갱신
    while (en < pt) {
        sum += rec[++en];
        sum -= rec[++st];
        if (sum > mx) { //합의 최댓값 저장
            mx = sum;
            ans = st;
        }
    }
}

string solution(string play_time, string adv_time, vector<string> logs) {

    setConditions(play_time, adv_time, logs);
    setRec();
    findStart();
    return tostr(ans);
}