[SlidingWindow] (프로그래머스 Lv 3) 광고 삽입

문제

• 문제 링크
• 문제 설명: 동영상 재생시간 길이 play_time, 공익광고의 재생시간 길이 adv_time, 시청자들이 해당 동영상을 재생했던 구간 정보 logs가 매개변수로 주어질 때, 시청자들의 누적 재생시간이 가장 많이 나오는 곳에 공익광고를 삽입하려고 합니다. 이때, 공익광고가 들어갈 시작 시각을 구해서 return 하도록 solution 함수를 완성해주세요. 만약, 시청자들의 누적 재생시간이 가장 많은 곳이 여러 곳이라면, 그 중에서 가장 빠른 시작 시각을 return 하도록 합니다.
  • 시작 시각이 여러 개면 가장 빠른 시작 시각을 반환
  • 누적 재생시간 = 재생 구간의 크기 * 재생한 사람 수

 

• 입력
  • play_time := 00:00:01 이상 99:59:59 이하
  • adv_time <= play_time
  • logs := "H1:M1:S1-H2:M2:S2"
  • logs 크기 <= 300,000
• 출력: 광고가 재생될 가장 빠른 시작 시각

play_time	adv_time	logs	result
"02:03:55"	"00:14:15"	["01:20:15-01:45:14", "00:40:31-01:00:00", "00:25:50-00:48:29", "01:30:59-01:53:29", "01:37:44-02:02:30"]	"01:30:59"
"99:59:59"	"25:00:00"	["69:59:59-89:59:59", "01:00:00-21:00:00", "79:59:59-99:59:59", "11:00:00-31:00:00"]	"01:00:00"
"50:00:00"	"50:00:00"	["15:36:51-38:21:49", "10:14:18-15:36:51", "38:21:49-42:51:45"]	"00:00:00"

풀이

• logs 배열의 크기가 최대 300,000 이므로 O(N) 만에 문제를 해결해야 함
• 간단하게 누적 재생시간을 계산하려면 해당 시간대에 재생된 사람 수를 카운트 해야 함
• play_time의 최대 시간을 초단위로 계산해보면 99*3600 + 59*60 + 59 = 359,999 로 배열의 크기가 크지 않음을 알 수 있음
• 따라서 모든 시간을 초 단위로 바꾼 뒤 매 로그마다 재생된 구간에 사람 수를 카운트해서 슬라이딩 윈도우로 O(N)만에 가장 빠른 시각을 구할 수 있음
• 주의할 점: 최대 로그 개수만큼 모든 구간이 재생되면 360000 * 300000 으로 32비트를 초과하므로 long long 자료형을 써야 함

#include <cstring>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;

// 시간 문자열을 초 단위로 변환하는 함수
int timeToSeconds(const string& time) {
    int hours = (time[0]-'0')*10 + (time[1]-'0');
    int minutes = (time[3]-'0')*10 + (time[4]-'0');
    int seconds = (time[6]-'0')*10 + (time[7]-'0');
    return hours*3600 + minutes*60 + seconds;
}

string solution(string play_time, string adv_time, vector<string> logs) {
    int seconds[360000];
    memset(seconds, 0, sizeof(seconds));
    for (auto& l : logs) {
        int start = timeToSeconds(l);
        int end = timeToSeconds(l.substr(9));
        for (int i = start; i < end; i++)
            seconds[i]++; // 끝 시간은 포함되지 않으므로 제외하고 재생 사람 수를 카운트
    }
    
    int playTime = timeToSeconds(play_time);
    int advTime = timeToSeconds(adv_time);
    int startTime = 0;
    ll sum = 0, maxSum;
    // 첫 광고시간동안 재생한 사람 수 누적합 계산
    for (int i = 0; i < advTime; i++) sum += seconds[i];
    maxSum = sum;
    // 한 칸씩 윈도우를 옮기면서 최댓값 탐색
    for (int i = advTime; i < playTime; i++) {
        sum = sum - seconds[i-advTime] + seconds[i];
        if (sum > maxSum) {
            startTime = i-advTime+1; // 최댓값이면 시작 시각 저장
            maxSum = sum;
        }
    }
    
    // 초 단위를 다시 문자열 포맷으로 변환
    string answer;
    int times[3] = {startTime / 3600, (startTime % 3600) / 60, (startTime % 3600) % 60};
    for (int i = 0; i < 3; i++) {
        int a = times[i] / 10, b = times[i] % 10;
        answer.push_back(a + '0');
        answer.push_back(b + '0');
        if (i < 2) answer.push_back(':');
    }
    
    return answer;
}