[ 프로그래머스 광고 삽입 (Lv3) ] (C++)

프로그래머스의 광고삽입(Lv3) 문제이다.

 

[ 문제풀이 ]

총 동영상의 길이 , 광고의 재생시간 그리고 시청자들의 광고 재생 시간이 주어졌을 때 누적 재생 시간이 가장 큰 곳에 광고를 삽입하기 위해서는, 광고를 어디에 삽입해야 하는지 그 시간을 구해야 하는 문제이다.

먼저, 주어진 시간들을 어떻게 관리할지부터 정답을 도출하는 과정까지 단계별로 알아가보자.

 

#1. '시간'의 관리

이 문제는 모든 것이 다 시간으로 주어진다. 총 동영상의 길이 , 광고의 재생길이 , 시청자들이 동영상을 재생하는 구간정보 모두 '시간'으로 주어진다. 그리고 그 시간은 "AA:BB:CC" 형태의 문자열로 주어진다.

우리의 눈으로 보기에는 이러한 형태가 편해보일지 몰라도 실제로 구현하는 과정에서는 이대로 관리하기는 쉽지 않다.

따라서 본인은 가장 먼저 이러한 시간들을 모두 하나의 단위로 통일을 해주었다.

바로 '초' 단위로 만들어 주었다.

"AA : BB : CC" 라는 시간이 주어졌다면 이를 초로 바꾸는 과정은 다음과 같다.

시간을 초로 만드는 과정 = AA * 3600 = H

분을 초로 만드는 과정 = BB * 60 = M

초를 초로 만드는 과정 = CC = S

"AA : BB : CC" 라는 문자열을 int형의 '초' 단위로 바꾼다면 H + M + S 가 된다.

이런식으로 가장 먼저 주어진 시간들을 모두 초 단위로 바꿔서 문제에 접근을 시작하였다.

코드로 확인하면 다음과 같다.

int Convert_Time_To_Int(string S)
{
	string SH = S.substr(0, 2);
	int Hour = stoi(SH) * 3600;
	string SM = S.substr(3, 2);
	int Minute = stoi(SM) * 60;
	string SS = S.substr(6, 2);
	int Second = stoi(SS);

	int Total = Hour + Minute + Second;
	return Total;	
}

위의 코드가 본인이 구현한 "AA:BB:CC"를 초로 만드는 과정이다.

매개변수로 주어진 string S가 "AA:BB:CC"라는 문자열을 의미한다고 생각하면 된다.

중간중간 섞여있는 ':'를 빼고 숫자부분만 추출해내서 초로 변환하는 과정이다.

물론 ! 가장 최종적으로는 정답을 다시 문자열로 바꾸는 과정도 진행해야 하는데 이는 가장 마지막에 이야기해보자.

 

#2. 정답도출을 위한 밑작업 - 재생 구간의 갯수 구하기

이제부터는 초로 변환한 시간들을 토대로, 어디에 광고를 삽입해야 좋은지 , 어떻게 하면 최적의 시간에 넣을 수 있는지를 쉽게 파악할 수 있게 밑작업을 시작해보자.

문제에서 주어졌듯이, 우리가 구해야하는 광고를 넣어야 하는 시점은 "누적 재생시간이 가장 많이 나오는 곳" 이다.

그럼 누적 재생시간을 한번 구할 것인데, 그 전에 누적 재생시간을 구하기 위해서 재생 구간의 갯수부터 구해보는 과정을 진행해보자. 쉽게 생각하기 위해서 하나의 예를 가지고 진행해보자.

동영상 재생시간 = 00:01:00 (60초)

공익광고 재생시간 = 00:00:20 (20초)

시청자들의 시청구간 = [ 9s ~ 20s , 15s ~ 25s , 30s ~ 40s , 33 ~ 40s , 35s ~ 50s ]

이 상황을 가정해보자. 그림으로 표현하면 다음과 같이 표현할 수 있다.

(편의상 모두 초로 변환했다고 가정하고 표현하겠습니다.)

위와 같이 표현할 수 있다. 그렇다면 누적 재생시간을 구하기 위해서 먼저, 재생 구간의 갯수부터 구해보자.

위의 그림을 보면 10s부터 15s까지는 재생구간이 1개라는 것을 알 수 있다.

그런데 ! 9s부터 시작된다고 했는데 왜 10s부터 누적 재생시간이 계산이 되는 것일까 ??

문제의 가장 아랫부분에 설명이 되어있듯이, "1초부터 10초까지 동영상이 재생되었다면 재생시간은 9초입니다." 라고 되어 있다. 즉 ! 1초부터 10초까지라면 총 10초가 되어야 하는데, 9초로 계산을 하므로, 이를 표현하기 위해서 편의상 1초 ~ 10초 동안 재생되었다고 한다면, 2초 ~ 10초인 9초동안 재생이 되었다고 계산을 하기 위함이다.

즉, 재생 시작시간 + 1초 ~ 재생이 끝나는 시간 이 실질적인 동영상의 재생 시간이라고 생각하면 쉽다.

그리고 16초부터 20초까지는 재생구간의 갯수가 2개가 된다. 왜냐하면 파랑색과 빨강색이 겹치기 때문이다.

31s ~ 33s 까지는 재생구간의 갯수가 1개.

34s ~ 35s 까지는 재생구간의 갯수가 2개.

36s ~ 40s 까지는 재생구간의 갯수가 3개.

41s ~ 50s 까지는 재생구간의 갯수가 1개.

이런식으로 재생 구간의 갯수를 모두 구해줄 수가 있다.

코드로 표현한다면 다음과 같이 표현할 수가 있다.

vector<int> Total_Play_Time(MAX, 0);
for (int i = 0; i < logs.size(); i++)
{
	int Start = Convert_Time_To_Int(logs[i].substr(0, 8));
	int End = Convert_Time_To_Int(logs[i].substr(9, 8));
	for (int j = Start + 1; j <= End; j++) Total_Play_Time[j]++;
}

여기서 하나 짚고 넘어가자. Total_Play_Time이라는 벡터는 크기가 'MAX'라고 설정되어 있는데 이 MAX는 얼마의 값을 가지고 있을까 ?? 바로 '360000' 이라는 값을 가지고 있다.

왜냐하면 주어진 동영상 재생시간의 최대시간은 99:59:59 인데, 이를 초로 변환하게 되면 359999 초가 나오게 된다. 따라서, 360000의 크기를 가진 벡터를 선언해주고, 이 벡터의 인덱스들을 하나의 '초' 라고 생각하고 계산할 수 있다.

 

#3. 재생누적시간 구하기

그럼 #2에서 구했던 재생구간의 갯수를 통해서 재생 누적시간을 구해보자.

그전에! #2에서 재생 구간의 갯수를 왜 구한 것일까 ?? 구하자고 했으니 구하긴 했는데 왜 구한 것일까 ?? 그리고 이를 통해서 어떻게 재생 누적시간을 구할 수 있는지부터 이야기를 해보자.

다시 그림을 가져와보자.

광고시간이 20초라고 했으니, 가장 먼저 9초에 광고를 삽입한다고 가정을 해보자.

9초에 광고를 삽입한다면, 이 광고는 총 몇초동안 재생이 되는 것일까 ???

9초에 광고를 삽입한다면 아마 이 광고는 9s ~ 29s 까지 재생이 될 것이다.

10s ~ 15s 구간 : 파랑색 시청자에 의해서 6초동안 광고재생

16s ~ 20s 구간 : 파랑색 + 빨강색 시청자에 의해서 10초동안 광고재생

여기서 ! 왜 16s ~ 20s는 5초인데 10초동안 광고가 재생되는 것일까 ???

왜냐하면 파랑색 시청자에 의해서도 광고가 재생되고 빨강색 시청자에 의해서도 광고가 재생되기 때문이다.

즉, 5s동안은 2군데에서 재생이 되므로 실질적으로 이 광고가 재생되는 시간은 10초라고 생각할 수 있는 것이다.

21s ~ 25s 구간 : 빨강색 시청자에 의해서 5초동안 광고재생

26s ~ 29s 구간 : 이 구간을 시청하는 시청자가 없으므로 0초동안 광고재생.

즉 ! 9s에 광고를 삽입한다면, 이 광고는 6s + 10s + 5s = 21s 동안 광고가 재생될 것이다.

이 '21s'라는 값이 가지는 의미를 적어보면 "9초에 광고를 삽입하면, 이 광고는 실질적으로 21초동안 재생되어 집니다." 를 의미한다.

그럼 바꿔서 30s에 광고를 삽입한다고 가정해보자. 그럼 다음과 같아질 것이다.

30s에 광고를 삽입한다면 아마 이 광고는 30s ~ 50s 까지 재생 될 것이다.

31s ~ 33s : 노랑색 시청자에 의해서 3초 동안 광고재생

34s ~ 35s : 노랑색 + 초록색 시청자에 의해서 4초동안 광고재생

36s ~ 40s : 노랑색 + 초록색 + 보라색 시청자에 의해 15초동안 광고재생

41s ~ 50s : 보라색 시청자에 의해 10초동안 광고재생

즉 ! 30s초에 광고를 삽입하게 된다면 3s + 4s + 15s + 10s = 32초 동안 광고가 재생됨을 의미한다.

그럼 이제 재생구간의 갯수가 재생 누적시간에 어떤 영향을 미치는지는 대략 알았을 것이다.

이러한 계산을 1초부터 광고가 들어갈 수 있는 최종적인 시간까지 모두 계산을 해보면 된다.

여기서 광고가 들어갈 수 있는 최종적인 시간은 "동영상 재생시간 - 광고시간 + 1"초가 된다.

예를 들어서 동영상이 100초이고 광고가 40초라고 한다면, 광고가 들어갈 수 있는 가장 최종적인 시간은

100 - 40 + 1 = 61s가 된다. 61초부터 100초까지 재생되는 시간이 광고가 재생될 수 있는 가장 마지막 시간이 될 것이다. 이 과정을 코드로 구현하면 다음과 같이 구현할 수 있다.

1.  long long Cur_Play_Time = 0;
2.  long long Max_Play_Time = 0;
3.  int Time = 1;
4.  for (int i = 1; i <= Adv_Time; i++)
5.  {
6.  	Cur_Play_Time += Total_Play_Time[i];
7.  	Max_Play_Time += Total_Play_Time[i];
8.  }

9.  for (int i = 2; i <= (Play_Time - Adv_Time + 1); i++)
10. {
11. 	Cur_Play_Time += (long long)(Total_Play_Time[i + Adv_Time - 1] - Total_Play_Time[i - 1]);
12. 	if (Cur_Play_Time > Max_Play_Time)
13. 	{
14. 		Max_Play_Time = Cur_Play_Time;
15. 		Time = i;
16. 	}
17. }

line4 ~ line8)의 반복문은 가장 초기값 설정을 위한 반복문이다. 0초에 광고를 삽입했다고 가정했을 때, 재생 누적시간이 되는 것이다. 반복문이 '1'부터 시작되는 것은 위에서도 이야기했듯이, 0초에 광고를 삽입하게 되면 실질적인 재생시간은 1초부터라고 생각하는 것이 계산이 편하기 때문이다. Total_Play_Time[] 이라는 변수는 #2에서 구해놓은 "재생구간의 갯수"를 저장해놓은 변수이다.

즉, "특정 시간에 광고가 재생되는 시간은, 해당 시간에 재생되고 있는 구간의 갯수에 비례해서 증가" 하게 된다.

line9)부터는 1초부터 "광고가 들어갈 수 있는 최종시간" 까지 매시간마다 광고를 모두 삽입해 보는 것이다.

line11)에서의 계산식은 다음과 같은 원리로 이루어져있다.

지금까지 우리가 했던 20초동안 재생되는 광고로 예를 들어보자.

line4 ~ 8)에 의해서 1초 ~ 20초 동안 광고가 실질적으로 재생된 재생누적시간이 Cur_Play_Time이라는 변수에 저장되어 있을 것이다. 편의상 1초 ~ 20초동안 광고가 실질적으로 재생된 재생누적시간을 'K' 라고 두자.

그럼, 2초 ~ 21초 동안 광고가 실질적으로 재생된 누적시간은 어떻게 계산을 하면 될까 ?? 다시 2초부터 하나하나 계산할 필요 없이, "K 라는 시간에서 21초 그 순간에서의 재생 구간의 갯수 만큼을 더해준 후에, 1초에서의 재생 구간의 갯수만큼만 빼주면" 된다. 그렇게 되면 2 ~ 21초 동안의 재생 누적 시간을 구할 수 있을 것이다.

이런식으로 모든 시간에 대해서 재생 누적시간을 구한 후, 재생누적시간이 가장 큰 시간을 저장해준다.

위의 코드에서는 line15)에서 Time이라는 변수가 이 값을 저장하고 있음을 확인할 수 있다.

중요한 것은 ! 우리는 모두 초로 변환 후에 계산을 했으므로 정답을 return 하기 위해서는 다시 string형태로 변환 해줘야 한다 !

[ 소스코드 ]

#include <string>
#include <vector>
 
#define MAX 360000
using namespace std;
 
int Convert_Time_To_Int(string S)
{
    string SH = S.substr(0, 2);
    int Hour = stoi(SH) * 3600;
    string SM = S.substr(3, 2);
    int Minute = stoi(SM) * 60;
    string SS = S.substr(6, 2);
    int Second = stoi(SS);
 
    int Total = Hour + Minute + Second;
    return Total;    
}
 
string Convert_Time_To_String(int T)
{
    string S = "";
    int Hour = T / 3600;
    int Minute = (T % 3600) / 60;
    int Second = T % 60;
 
    if (Hour <= 9) S += '0';
    S += to_string(Hour);
    S += ':';
    if (Minute <= 9) S += '0';
    S += to_string(Minute);
    S += ':';
    if (Second <= 9) S += '0';
    S += to_string(Second);
    return S;
}
 
 
string solution(string play_time, string adv_time, vector<string> logs) 
{
    string answer = "";
    int Play_Time = Convert_Time_To_Int(play_time);
    int Adv_Time = Convert_Time_To_Int(adv_time);
 
    vector<int> Total_Play_Time(MAX, 0);
    for (int i = 0; i < logs.size(); i++)
    {
        int Start = Convert_Time_To_Int(logs[i].substr(0, 8));
        int End = Convert_Time_To_Int(logs[i].substr(9, 8));
        for (int j = Start + 1; j <= End; j++) Total_Play_Time[j]++;
    }
 
    long long Cur_Play_Time = 0;
    long long Max_Play_Time = 0;
    int Time = 1;
    for (int i = 1; i <= Adv_Time; i++)
    {
        Cur_Play_Time += Total_Play_Time[i];
        Max_Play_Time += Total_Play_Time[i];
    }
    for (int i = 2; i <= (Play_Time - Adv_Time + 1); i++)
    {
        Cur_Play_Time += (long long)(Total_Play_Time[i + Adv_Time - 1] - Total_Play_Time[i - 1]);
        if (Cur_Play_Time > Max_Play_Time)
        {
            Max_Play_Time = Cur_Play_Time;
            Time = i;
        }
    }
    answer = Convert_Time_To_String(Time - 1);
    return answer;
}