프로그래머스 - 광고삽입

일단 보자마자 쉽지 않겠다는 생각이 들었던 문제.
문자열 처리도 해야 하는 것 같고, 가장 많은 시청자가 보고 있다는 것을 어떻게 구분할 것인지도 고민해 봐야 하는, 생각할 거리가 꽤 많은 문제였던 것 같다.

문제 풀이 회고

1. 자잘하게 신경써야 하는 부분이 많았다.

• 시청 구간은 기본적으로 이상, 미만으로 정의되어서 마지막 시점은 광고 시청 시간에는 포함되지 않는다는 것
• 공익광고 재생 시점과 재생 시간을 더한 뒤 1을 빼 줘야 하는 점 등등..

2. 샘플 테스트케이스를 보고 대충 때려맞추려고 하지 말자.

• 문제 설명에 나와있는 그림을 보고, 어림짐작으로 왠지 답은 항상 사용자 시청 구간의 시작점 중 하나일 것 같다!라고 비약을 한 상태로 문제를 풀다보니, 틀린 원인을 찾는데 시간이 꽤 걸렸다... (사실 시청 구간의 개수도 300,000개나 되어서 성능적 차이도 별로 없었다...)
  비약은 항상 조심하도록 하자.
  비약이 들어맞는 경우에는 풀이 시간이 단축되지만, 비약이 틀린 경우에는 그 이상의 시간 손해를 보게 될 것이다.

정답 접근 과정

1. 우선 문자열 처리부터

사실 문제를 본격적으로 풀기 전에 일단 문자열 처리부터 해야겠다는 생각이 들었다.

HH:MM:SS와 같은 형식의 문자열을 그대로 가지고 시청 구간의 길이를 구해 볼 수도 있지만, 그렇게 문제를 풀면 너무 큰 스트레스를 받을 것이 분명했다.

다행히 시간을 나타내는 문자열 형식과 길이가 고정되어 있어서, 비교적 간단하게 하나의 long long(사실 처음에 int로 했다가 계속 틀려서 게시판을 확인하고 나서야 고쳤다...) 변수로 변환시킬 수 있었다.

변환한 long long값을 다시HH:MM:SS 형식의 문자열로 되돌리는 함수도 미리 만들어 두었다.

2. 시간 복잡도 계산

logs에 들어오는 시청 구간의 최대 개수는 300, 000개.

공익 광고 재생 시간과 동영상 플레이 타임의 최대치는 거의 100시간(360, 000 초), 각 시청 기록은 동영상 재생 시간 안쪽에 들어오므로, 이 역시도 대략 100시간(360, 000 초)정도 된다.

따라서 이 문제에서 사용해야 하는 알고리즘의 시간 복잡도는 아마 O(NlgN) 이하가 되어야 할 것이다.

O(NlgN)이라고 하면, 보통 정렬이나 힙을 떠올리게 되는데, 아무래도 힙은 사용하기 쉽지 않아 보였고, 정렬을 사용한다고 가정하면 그리디를 써 봐야겠다는 생각도 잠깐 해 보았다.

3. 특정 구간의 공익 광고 시청 시간을 구하는 방법

광고 시청 구간의 길이가 최대 100,000초를 넘고, 공익 광고 재생 시간도 100,000초가 넘기 때문에 두 구간의 겹치는 부분에 대해 for문을 돌면서 일일히 시청시간을 카운팅하는 방법은 최대한 피해야겠다는 생각을 했다.

for문을 돌면서 거의 O(N) 시간 복잡도를 사용하고, 만약 광고 시청 구간이 촘촘히 몰려있는 테스트케이스의 경우 시간 복잡도가 거의 O(N^2)이 되어버리기 때문이다.

특정 구간의 시청 시간을 O(1)으로 찾을 수 있으면 좋겠다 생각했고, 여기에서 누적합 아이디어가 떠올랐다.
(누적합은 O(N) 연산 한번을 수행한 이후로, 특정 구간의 포함되는 원소들의 합을 O(1)로 찾을 수 있게 해 준다.)

누적합을 이용하기 위해서 구간 정보(광고 시청 구간, 공익 광고 재생 구간)을 표현하는 방법을 고안하기 시작했다.

4. 구간 정보(광고 시청 구간, 공익 광고 재생 구간)의 표현

우선, 데이터의 형태가 시간이므로, 1차원 배열에서 누적합을 사용하기 위한 방법을 고민했다.

1. 전체 동영상 재생 구간을 하나의 큰 배열로 잡는다.(0으로 초기화)

2. 각 광고 시청 구간에 대해, 배열의 [시작 시점, 끝시점)에 해당하는 인덱스에 시청자수를 +1 해준다.

• 단, 구간마다 for문을 돌게되면 시간복잡도가 여기에서 O(N^2)이 되어버린다.
  누적합을 이용하여, 시청 구간 데이터 삽입은 처음 지점과 끝 지점에만 하고, 모든 시청 구간 정보를 삽입한 뒤 전체 배열을 한번 for문을 돌면서 배열을 완성한다.

3. 이렇게 되면, 각 배열의 원소(각 시점)에는 그 시점에 동영상을 시청하고 있는 시청자 수가 저장된다.

5. 공익광고 시청자 수를 최대로 만드는 광고 재생 시점 구하기

처음에 문제를 풀 때, 최적의 재생 시점은 항상 시청 구간의 시작점들 중 하나다!라고 비약하고 들어가서 풀이가 순탄치 못했다.

배열의 전체 길이가 그렇게 크지 않기 때문에, 00:00:00시점부터 가능한 끝시점까지 모든 경우의 수를 탐색하는 것이 정석적인 풀이 방법이 되겠다.

슬라이딩 윈도우 기법을 활용한다.

• 00:00:00 시점부터(배열의 0번 인덱스) 가능한 끝 시점까지 윈도우를 움직인다.(O(N))
• 윈도우 안으로 들어오는 배열의 원소(각 시점의 시청자 수)의 합을 누적합을 통해 구한다.(O(1))
• 구한 누적합이 최고 기록을 갱신할 때마다 정답도 현재 윈도우의 시작점으로 갱신한다.
• 시간복잡도는 O(N)이 된다.

코드

#include <string>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>

using namespace std;
typedef long long ll;

ll arr[360015];
ll prefix[360015];

ll timeToInt(string timeData)
{
    int hour = stoi(timeData.substr(0, 2));
    int minute = stoi(timeData.substr(3, 5));
    int second = stoi(timeData.substr(6));
    return 3600 * hour + 60 * minute + second;
}

string itos(ll k)
{
    string ret = "";
    while(k > 0)
    {
        ret += ('0' + (k % 10));
        k /= 10;
    }
    reverse(ret.begin(), ret.end());
    return ret;
}

string formatting(string str)
{
    string ret = "";
    for(int i = 0; i < 2 - str.size(); i++)
        ret += '0';
    return ret + str;
}

string intToTime(ll t)
{
    string hour = itos(t / 3600); t %= 3600;
    string minute = itos(t / 60); t %= 60;
    string second = itos(t);
    return formatting(hour)+":"+formatting(minute)+":"+formatting(second);
}

pair<ll, ll> splitTime(string& str) {
    return {timeToInt(str.substr(0, 8)), timeToInt(str.substr(9))};
}

string solution(string play_time, string adv_time, vector<string> logs) {
    vector<pair<ll, ll>> times; 
    for(int i = 0; i < logs.size(); i++)
    {
        times.push_back(splitTime(logs[i]));
        arr[times[i].first] += 1;
        arr[times[i].second] -= 1;
    }
    
    ll cur = 0;
    for(int i = 0; i < 360005; i++)
    {
        cur += arr[i];
        arr[i] = cur;
    }
    
    prefix[0] = arr[0];
    for(int i = 1; i < 360005; i++)
        prefix[i] += (prefix[i - 1] + arr[i]);
    times.push_back({0, 0});
    
    ll sum = 0;
    ll ans = 0;
    ll duration = timeToInt(adv_time);
    for(int i = 0; i < 360015 - duration + 1; i++)
    {
        ll acc = prefix[i + duration - 1] - prefix[i] + arr[i];
        if(acc > sum)
        {
            ans = i;
            sum = acc;
        }
    }
    return intToTime(ans);
}