2021 KAKAO BLIND RECRUITMENT / 광고 삽입

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

프로그래머스

#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>

using namespace std;


long long time_table[360001];
long long ans_time;
int ans_start;


int conv(string log, int &start, int &end) {
    // H1:M1:S1-H2:M2:S2
    int hh1 = 10 * log[0] + log[1] - 11 * '0';
    int mm1 = 10 * log[3] + log[4] - 11 * '0';
    int ss1 = 10 * log[6] + log[7] - 11 * '0';
    start = hh1 * 3600 + mm1 * 60 + ss1;

    if (log.size() > 9) {
        int hh2 = 10 * log[9] + log[10] - 11 * '0';
        int mm2 = 10 * log[12] + log[13] - 11 * '0';
        int ss2 = 10 * log[15] + log[16] - 11 * '0';
        end = hh2 * 3600 + mm2 * 60 + ss2;
    }

    return start;
}


string conv(int t) {
    string time = "00:00:00";
    int h = t / 3600; t = t % 3600;
    int m = t / 60; t = t % 60;
    int s = t;

    time[0] += h / 10;
    time[1] += h % 10;
    time[3] += m / 10;
    time[4] += m % 10;
    time[6] += s / 10;
    time[7] += s % 10;
    return time;
}


void update(int start, int adv) {
    long long elapsed = time_table[start + adv] - time_table[start];

    if (ans_time == elapsed)
        ans_start = min(ans_start, start);

    if (ans_time < elapsed) {
        ans_time = elapsed;
        ans_start = start;
    }
}


void f(vector<string>& logs, int cur, int adv, int play) {
    int start, end;
    conv(logs[cur], start, end);

    start = min(start, play - adv);
    update(start, adv);

    start = max(end - adv, 0);
    update(start, adv);
}


void makeTable(int play, int adv, vector<string> &logs) {
    for (auto a : logs) {
        int s, e;
        conv(a, s, e);

        time_table[s + 1]++;
        time_table[e + 1]--;
    }

    int d = time_table[0];
    for (int i = 1; i <= play; ++i) {
        d += time_table[i];
        time_table[i] = time_table[i - 1] + d;
    }
    
    /*for (int i = 1; i <= play; ++i) time_table[i] += time_table[i - 1];
    for (int i = 1; i <= play; ++i) time_table[i] += time_table[i - 1];*/
}


string solution(string play_time, string adv_time, vector<string> logs) {
    sort(logs.begin(), logs.end());

    int adv = conv(adv_time, adv, adv);
    int play = conv(play_time, play, play);

    makeTable(play, adv, logs);

    for (int i = 0; i < logs.size(); ++i) {
        f(logs, i, adv, play);
    }

    return conv(ans_start);
}

- 누적합 적용을 두 번 반복하는 방식

int d = time_table[0];
for (int i = 1; i <= play; ++i) {
    d += time_table[i];
    time_table[i] = time_table[i - 1] + d;
}

// 누적합 적용 - 동일한 결과

for (int i = 1; i <= play; ++i) time_table[i] += time_table[i - 1];
for (int i = 1; i <= play; ++i) time_table[i] += time_table[i - 1];

- long long 고려