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

2021 카카오 코딩 테스트 문제입니다.

 

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

문제 확인

 

초로 환산했을 때 최대 크기가 360000이므로 배열과 prefix sum을 이용하여 풀 수 있습니다.

 

풀이

 

들어오는 string은 모두 길이가 고정이므로 간단하게 시간과 정수로 변환하는 함수를 만들어 활용합니다.

log가 시작되는 지점에 +1, 끝나는 지점에 -1을 해 두고 이들을 prefix sum을 구하여 각 시간마다 시청하는 사람의 수를 O(n) 만에 구할 수 있습니다.

예를 들어 log가 0~1, 2~8, 3~6 로 나올 경우 배열은 다음과 같습니다.

ary[i]+=ary[i-1] 로 간단하게 prefix sum을 구할 수 있으며 구간의 총 시간 합은 ary[start] + ~ ary[start + adv_len]이 됩니다.

 

매 구간마다 합을 구하게 되면 많은 시간이 걸리므로 다음 구간으로 넘어가는 경우 값을 ary[end] - ary[start] 만큼 더하여 갱신해주면 빠르게 다음 구간의 합을 구할 수 있습니다.

 

코드

#include <iostream>
#include <vector>
#include <string>
using namespace std;
 
inline int time_to_int(string &t, int i) {
    int res = 0;
    res += (t[i] - '0') * 36000;
    res += (t[i + 1] - '0') * 3600;
 
    res += (t[i + 3] - '0') * 600;
    res += (t[i + 4] - '0') * 60;
 
    res += (t[i + 6] - '0') * 10;
    res += (t[i + 7] - '0');
    return res;
}
inline string int_to_time(int t) {
    char tmp[9];
    sprintf(tmp, "%02d:%02d:%02d", t / 3600, t / 60 % 60, t % 60);
    
    return string(tmp);
}
 
string solution(string play_time, string adv_time, vector<string> logs) {
    int ary[360001] = { 0 };
    for (auto &t : logs) {
        int s = time_to_int(t, 0), e = time_to_int(t, 9);
        ary[s]++;
        ary[e]--;
    }
    long long max_val, cur_val = ary[0];
    int max_start = 0,    total = time_to_int(play_time, 0), adv_len = time_to_int(adv_time, 0);
    for (int i = 1; i < adv_len; i++) {
        ary[i] += ary[i - 1];
        cur_val += ary[i];
    }
    for (int i = adv_len; i <= total; i++)
        ary[i] += ary[i - 1];
    max_val = cur_val;
 
    for (int start = 0, end = adv_len; end <= total; start++, end++) {
        cur_val += ary[end] - ary[start];
        if (max_val < cur_val) {
            max_val = cur_val;
            max_start = start + 1;
        }
    }
 
    return int_to_time(max_start);
}
int main() {
    vector<string> arr = { "00:00:00-00:00:10"};
 
    cout << solution("99:59:59", "00:00:10", arr);
 
}
 

정확성 테스트

테스트 1 〉	통과 (0.91ms, 5.32MB)
테스트 2 〉	통과 (1.13ms, 5.73MB)
테스트 3 〉	통과 (1.55ms, 6.27MB)
테스트 4 〉	통과 (5.11ms, 12.8MB)
테스트 5 〉	통과 (9.61ms, 20.8MB)
테스트 6 〉	통과 (1.42ms, 5.23MB)
테스트 7 〉	통과 (17.59ms, 36.9MB)
테스트 8 〉	통과 (17.36ms, 36.9MB)
테스트 9 〉	통과 (25.36ms, 53.1MB)
테스트 10 〉	통과 (26.50ms, 53.3MB)
테스트 11 〉	통과 (26.65ms, 53.2MB)
테스트 12 〉	통과 (25.14ms, 53.2MB)
테스트 13 〉	통과 (25.99ms, 53.3MB)
테스트 14 〉	통과 (22.34ms, 53.1MB)
테스트 15 〉	통과 (0.98ms, 5.19MB)
테스트 16 〉	통과 (22.43ms, 53.2MB)
테스트 17 〉	통과 (25.73ms, 53.2MB)
테스트 18 〉	통과 (25.10ms, 53.2MB)
테스트 19 〉	통과 (0.85ms, 5.11MB)
테스트 20 〉	통과 (0.79ms, 5.25MB)
테스트 21 〉	통과 (7.50ms, 20.7MB)
테스트 22 〉	통과 (7.75ms, 20.7MB)
테스트 23 〉	통과 (25.87ms, 53.1MB)
테스트 24 〉	통과 (22.86ms, 53.2MB)
테스트 25 〉	통과 (1.18ms, 5.08MB)
테스트 26 〉	통과 (0.97ms, 5.13MB)
테스트 27 〉	통과 (1.00ms, 5.15MB)
테스트 28 〉	통과 (1.02ms, 5.16MB)
테스트 29 〉	통과 (0.95ms, 5.18MB)
테스트 30 〉	통과 (1.07ms, 5.23MB)
테스트 31 〉	통과 (0.96ms, 5.11MB)

채점 결과

정확성: 100.0

합계: 100.0 / 100.0