[알고리즘 풀이 분석] 프로그래머스 광고 삽입 (2021 Kakao Blind Recruitment)

오늘 아주 지독한 놈을 풀었다,,, 탈탈 털렸지만,, 각오 했고 시험 보고 바로 복기 왜 안했나 싶었다. 그때 했으면 지금 내가 좀 더 잘 하지 않았을까,,?ㅜ

오늘 풀어본 문제는 프로그래머스 광고 삽입 이다. 올해 상반기 카카오 공채 1차 시험 문제이고 5번문제다. 문제를 봤던 기억이 난다. 하지만 5번 문제인 만큼 읽었을 때 시간도 부족했고 시간을 어떻게 처리할지 힘들었던 것 같다.

시험이라 생각하고 30분 정도 고민을 해 보았는데, 그리디로 풀어야 하나,, 고민하다가 시간이 많이 흘러가면서 해설을 보고 구현하였다. 카카오 코테 목표에 5번까지 해결할 욕심은 사실 크게 없기에 해설을 보고 정확하게 구현하는 연습을 하자 마음 먹었다!

시간, 분, 초를 처리하는 방법을 배울 수 있엇고 누적 값을 이용해 원하는 구간의 값을 도출해 내는 방법을 배웠다!

프로그래머스 광고 삽입

카카오TV에서 유명한 크리에이터로 활동 중인 죠르디는 환경 단체로부터 자신의 가장 인기있는 동영상에 지구온난화의 심각성을 알리기 위한 공익광고를 넣어 달라는 요청을 받았습니다. 평소에 환경 문제에 관심을 가지고 있던 "죠르디"는 요청을 받아들였고 광고효과를 높이기 위해 시청자들이 가장 많이 보는 구간에 공익광고를 넣으려고 합니다. "죠르디"는 시청자들이 해당 동영상의 어떤 구간을 재생했는 지 알 수 있는 재생구간 기록을 구했고, 해당 기록을 바탕으로 공익광고가 삽입될 최적의 위치를 고를 수 있었습니다.
참고로 광고는 재생 중인 동영상의 오른쪽 아래에서 원래 영상과 동시에 재생되는 PIP(Picture in Picture) 형태로 제공됩니다.

다음은 "죠르디"가 공익광고가 삽입될 최적의 위치를 고르는 과정을 그림으로 설명한 것입니다.

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

입출력

• play_time, adv_time은 길이 8로 고정된 문자열입니다.

  • play_time, adv_time은 HH:MM:SS 형식이며, 00:00:01 이상 99:59:59 이하입니다.
  • 즉, 동영상 재생시간과 공익광고 재생시간은 00시간 00분 01초 이상 99시간 59분 59초 이하입니다.
  • 공익광고 재생시간은 동영상 재생시간보다 짧거나 같게 주어집니다.

• logs는 크기가 1 이상 300,000 이하인 문자열 배열입니다.

  • logs 배열의 각 원소는 시청자의 재생 구간을 나타냅니다.
  • logs 배열의 각 원소는 길이가 17로 고정된 문자열입니다.
  • logs 배열의 각 원소는 H1:M1:S1-H2:M2:S2 형식입니다.
    • H1:M1:S1은 동영상이 시작된 시각, H2:M2:S2는 동영상이 종료된 시각을 나타냅니다.
    • H1:M1:S1는 H2:M2:S2보다 1초 이상 이전 시각으로 주어집니다.
    • H1:M1:S1와 H2:M2:S2는 play_time 이내의 시각입니다.

• 시간을 나타내는 HH, H1, H2의 범위는 00~99, 분을 나타내는 MM, M1, M2의 범위는 00~59, 초를 나타내는 SS, S1, S2의 범위는 00~59까지 사용됩니다. 잘못된 시각은 입력으로 주어지지 않습니다. (예: 04:60:24, 11:12:78, 123:12:45 등)

• return 값의 형식
  공익광고를 삽입할 시각을 HH:MM:SS 형식의 8자리 문자열로 반환합니다.

풀이

풀이는 kakao Tech 블로그의 해설 을 참고하였다.

기본적으로 DP 즉, memozation 아이디어를 기반으로 이루어진다. 제한사항에 동영상 재생 시간은 최대 99시간 59분 59초 이고 이는 최대 100*60*60 = 360000 초를 의미한다.

문제에 접근하는 가장 첫 단계는 모든 시간을 동일하게 초로 다루는 것이었다. 각 시청자가 시청을 시작하는 시간, 종료하는 시간, 광고가 삽입될 시간, 종료될 시간을 동일하게 초로 환산해서 사이즈가 360000인 1차원 배열로 접근하여 memozation 하는 것이 핵심 접근 방법인 것 같다.

그렇다면 도대체 무엇을 memozation 하는가?
결론부터 말하자면 누적 시청 횟수를 의미한다. 배열 videoTime은 360000 의 크기를 가진다. 즉 매초마다 무엇인가가 기록된다는 의미이다. 시청자가 만약 0부터 3초 동안 동영상을 본다면 videoTime[0], videoTime[1], videoTime[2] 에 각 초마다 기록된다.

우리의 목표는 배열 videoTime[i] 에 i 초까지 누적된 총 시청 횟수를 기록하는 것이다. 이후 i초~j초 까지 총 시청 횟수가 몇번인지를 구하고자 하면 이는 j초까지의 누적 시청 횟수 - i초 까지의 누적 시청 횟수 와 같이 도출할 수 있다.

나는 이 아이디어를 설명을 보며 이해하는것도 그리 쉽지 않았다. 뭐 내 아이디어가 아니니 당연하겠지만, 역시 더 많은 접근 경험이 필요하구나,, 깨달았다 ㅜㅡㅜ

시청자 출입 기록하기

배열 videoTime 를 완성하기 위해 먼저 각 시청자의 출입을 기록해야 한다. i번째 시청자의 시청 시작 시간 logsStartSec[i] 에는 시청자를 추가 하고, 시청 종료 시간 logsEndSec[i] 에는 시청자를 뺀다.

// 시청 시작 시간, 종료 시간 출입 기록하기

for (long long i = 0; i < n; ++i){ 
    videoTime[logsStartSec[i]] += 1;
    videoTime[logsEndSec[i]] -= 1;
}

각 1초 마다 시청자 합 기록하기

이제 매 초마다, 즉 i초~i+1초 마다 해당 1초 동안 몇명이 동영상을 보는지 기록한다. 시간의 흐름에 따라 시청자의 출입을 누적해서 계산해 주면 되는데 매우 간단하지만 내가 과연 이걸 떠올릴 수 있을까,,? 의문이 들었다 ㅜ

// i~i+1 에 시청한 시청자 수 구하기
for (long long i = 1; i < playTImeSec; ++i) {
    videoTime[i] += videoTime[i-1];
}

누적 시청 횟수 기록하기

이제 각 초마다 몇명이 봤는지 도출이 되었고 이를 바탕으로 i초 까지의 총 시청 횟수를 누적하여 구한다.

// 0~i 초까지 누적 시청자 수 구하기
for (long long i = 1; i < playTImeSec; ++i) {
    videoTime[i] += videoTime[i-1];
}

이렇게 완성된 배열 videoTime은 모든 x 초 까지 누적된 시청 횟수를 의미 한다. 이후 동영상 재생 시작 시간부터 광고 삽입 가능한 시간 playTImeSec(동영상 총 시간)-advTimeSec(광고 시간) 까지 모든 구간별로 누적 시청 횟수가 가장 많은 구간을 찾아내고 해당 시작 시간을 8자리 반환 형식 HH:MM:SS 에 맞게 반환하면 된다.

이러한 과정을 거쳐 코드를 완성하고 제출 했을 때 테스트 케이스 17번만 통과하지 못했는데 질문 리스트를 보니 17번만 통과하지 못하는 경우 자료형을 int 보다 크게 바꿔주라는 글이 있었다. 모든 자료형을 int 대신 long long 으로 바꾼 뒤 통과할 수 있었는데 사실 조금 이해가 안된다,,

int 형 변수에 들어갈 수 있는 가장 큰 값을 생각해보면 360000인데, 더하고 빼고,, 하는 과정에서 int 오버플로가 발생한단 소리인데,, 이부분은 좀 더 고민을 해 봐야겠다,,

코드

#include <string>
#include <vector>

using namespace std;

string solution(string play_time, string adv_time, vector<string> logs) {
    int n = logs.size();

    long long maxTime = 360000;
    long long playTImeSec = 3600*stoi(play_time.substr(0,2)) + 60*stoi(play_time.substr(3,2)) + stoi(play_time.substr(6,2));
    long long advTimeSec = 3600*stoi(adv_time.substr(0,2)) + 60*stoi(adv_time.substr(3,2)) + stoi(adv_time.substr(6,2));

    vector<long long> logsStartSec(n);
    vector<long long> logsEndSec(n);
    vector<long long> videoTime(maxTime, 0);

    // 시작 시간, 종료 시간 변환
    for (int i = 0; i < n; ++i) {
        long long start = 3600*stoi(logs[i].substr(0,2)) + 60*stoi(logs[i].substr(3,2)) + stoi(logs[i].substr(6,2));
        long long end = 3600*stoi(logs[i].substr(9,2)) + 60*stoi(logs[i].substr(12,2)) + stoi(logs[i].substr(15,2));
        logsStartSec[i] = start;
        logsEndSec[i] = end;
    }

    // 시작 시간, 종료 시간 출입 기록하기
    for (int i = 0; i < n; ++i) {
        videoTime[logsStartSec[i]] += 1;
        videoTime[logsEndSec[i]] -= 1;
    }

    // i~i+1 에 시청한 시청자 수 구하기
    for (int i = 1; i < playTImeSec; ++i) {
        videoTime[i] += videoTime[i-1];
    }

    // 0~i 초까지 누적 시청자 수 구하기
    for (int i = 1; i < playTImeSec; ++i) {
        videoTime[i] += videoTime[i-1];
    }

    long long adStart;
    long long total = 0;
    for (long long i = 0; i <= playTImeSec-advTimeSec; ++i) {
        long long s = i, e = i+advTimeSec;
        long long sum  = videoTime[e-1];
        if (s>0){
            sum -= videoTime[s-1];
        }

        if (total < sum){
            adStart = s;
            total = sum;
        }
    }

    // total -> 형식에 맞게 변환
    int h = adStart/3600;
    adStart = adStart%3600;

    int m = adStart/60;
    adStart = adStart%60;

    int s = adStart;

    string answer = "";
    if (h<10){
        answer += "0";
    }
    answer += to_string(h);
    answer += ":";

    if (m<10){
        answer += "0";
    }

    answer += to_string(m);
    answer += ":";

    if (s<10){
        answer += "0";
    }
    answer += to_string(s);

    return answer;
}