[프로그래머스/Level 3/C++/2021 카카오 블라인드 채용] 광고 삽입
https://school.programmers.co.kr/learn/courses/30/lessons/72414
- 출처 : 프로그래머스 코딩 테스트 연습
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
[문제 요약]
- 다음은 "죠르디"가 공익광고가 삽입될 최적의 위치를 고르는 과정을 그림으로 설명한 것입니다.
- 그림의 파란색 선은 광고를 검토 중인 "죠르디" 동영상의 전체 재생 구간을 나타냅니다.
- 위 그림에서, "죠르디" 동영상의 총 재생시간은 02시간 03분 55초 입니다.
- 그림의 검은색 선들은 각 시청자들이 "죠르디"의 동영상을 재생한 구간의 위치를 표시하고 있습니다.
- 검은색 선의 가운데 숫자는 각 재생 기록을 구분하는 ID를 나타냅니다.
- 검은색 선에 표기된 왼쪽 끝 숫자와 오른쪽 끝 숫자는 시청자들이 재생한 동영상 구간의 시작 시각과 종료 시각을 나타냅니다.
- 위 그림에서, 3번 재생 기록은 00시 25분 50초 부터 00시 48분 29초 까지 총 00시간 22분 39초 동안 죠르디의 동영상을 재생했습니다.
- 위 그림에서, 1번 재생 기록은 01시 20분 15초 부터 01시 45분 14초 까지 총 00시간 24분 59초 동안 죠르디의 동영상을 재생했습니다.
- 그림의 빨간색 선은 "죠르디"가 선택한 최적의 공익광고 위치를 나타냅니다.
- 만약 공익광고의 재생시간이 00시간 14분 15초라면, 위의 그림처럼 01시 30분 59초 부터 01시 45분 14초 까지 공익광고를 삽입하는 것이 가장 좋습니다. 이 구간을 시청한 시청자들의 누적 재생시간이 가장 크기 때문입니다.
- 01시 30분 59초 부터 01시 45분 14초 까지의 누적 재생시간은 다음과 같이 계산됩니다.
- 01시 30분 59초 부터 01시 37분 44초 까지 : 4번, 1번 재생 기록이 두차례 있으므로 재생시간의 합은 00시간 06분 45초 X 2 = 00시간 13분 30초
- 01시 37분 44초 부터 01시 45분 14초 까지 : 4번, 1번, 5번 재생 기록이 세차례 있으므로 재생시간의 합은 00시간 07분 30초 X 3 = 00시간 22분 30초
- 따라서, 이 구간 시청자들의 누적 재생시간은 00시간 13분 30초 + 00시간 22분 30초 = 00시간 36분 00초입니다.
- "죠르디"의 동영상 재생시간 길이 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자리 문자열로 반환합니다.
[문제 풀이]
광고의 누적 재생시간이 가장 많이 나올려면 시청자가 많은 시간대에 광고를 배치하는 것이 가장 이상적일 것이다.
또한, 광고는 딱 한번만 영상에 들어가기 때문에 시청자가 가장 많은 시간대를 알아내야 할 필요가 있다.
매개변수로 주어지는 play_time의 최대가 99시간 59분 59초다. 이 값을 초로 변환하면 (360000-1)초가 되서 1차원 배열을 이용했고, logs에 주어지는 시청자들의 시작시간과 종료시간을 앞에 배열에 표시하여 시청자가 가장 몰리는 시간대를 누적합을 이용해 찾았다.
처음에 logs의 원소 하나당 time_table[시작시간(초)] ~ time_table[종료시간(초)]의 값들을 하나씩 증가시킨 다음 누적합 형태로 만들어 접근했으나, 배열 자체가 워낙 크기 때문에 시간초과가 났었다.
그래서 전체 구간의 값들을 다 증가시키않고 시작과 끝만 증가시켜서 누적합을 2번 진행해주면 시간은 줄어들면서 같은 결과를 만들었다.
2번째 표가 의미하는 것은 그 구간에서 시청하는 시청자의 수를 의미한다.
하지만 우리가 원하는 것은 누적재생횟수를 구해야 하기 때문에 누적합을 한번 더 진행해준다.
이제 이 표를 이용하여 답을 구할 수 있다.
예를 들어 광고가 3초짜리 광고라 했을 때 확인 하는 구간들은
(1초~3초), (2초~4초), (3초~5초), (4초~6초), (5초~7초), (6초~8초), (7초~9초)
- time_table[3초] - time_table[1초] = 3초
- time_table[4초] - time_table[2초] = 5초
- time_table[5초] - time_table[3초] = 6초
- time_table[6초] - time_table[4초] = 5초
- time_table[7초] - time_table[5초] = 4초
- time_table[8초] - time_table[6초] = 3초
- time_table[9초] - time_table[7초] = 1초
이렇게 구간 별 누적 재생시간을 구할 수 있고 3초일때 광고를 넣기 최고의 시간인 것이다.
[소스 코드]
#include <string>
#include <vector>
#include <iostream>
using namespace std;
vector<vector<long long>> make_time(string time)
{
vector<vector<long long>> log_time;
vector<long long> start_time;
vector<long long> end_time;
string tmp;
bool flag=false;
for(int i=0; i<time.size(); i++)
{
char letter = time.at(i);
if(letter >= '0' && letter <= '9') tmp.push_back(letter);
else if(letter == ':')
{
if(!flag)
{ start_time.push_back(atol(tmp.c_str())); tmp.clear(); }
else
{ end_time.push_back(atol(tmp.c_str())); tmp.clear(); }
}
else if(letter == '-')
{
start_time.push_back(atol(tmp.c_str())); tmp.clear();
flag = true;
}
}
if(tmp.size() != 0) end_time.push_back(atol(tmp.c_str()));
log_time.push_back(start_time);
log_time.push_back(end_time);
return log_time;
}
long long hour_to_sec(vector<long long> &time)
{
return (time[0] * 3600 + time[1] * 60 + time[2]);
}
string sec_to_hour(int time)
{
string tmp;
if(time / 3600 >= 10) { tmp=tmp+to_string(time/3600); tmp.push_back(':');time%=3600;}
else {tmp.push_back('0'); tmp=tmp+to_string(time/3600); tmp.push_back(':'); time%=3600;}
if(time / 60 >= 10) {tmp=tmp+to_string(time/60); tmp.push_back(':');time%=60;}
else {tmp.push_back('0'); tmp=tmp+to_string(time/60); tmp.push_back(':');time%=60;}
if(time >= 10) {tmp=tmp+to_string(time); }
else {tmp.push_back('0'); tmp=tmp+to_string(time);}
return tmp;
}
string solution(string play_time, string adv_time, vector<string> logs) {
string answer = "";
vector<long long> time_table;
vector<vector<vector<long long>>> log_time;
for(int i=0;i<logs.size(); i++) log_time.push_back(make_time(logs[i]));
string tmp = play_time + "-" + adv_time;
vector<vector<long long>> tmp2 = make_time(tmp);
vector<long long> play_time_int = tmp2[0];
vector<long long> adv_time_int = tmp2[1];
time_table.resize(hour_to_sec(play_time_int)+1);
for(int i=0; i<log_time.size(); i++)
{
long long start_sec = hour_to_sec(log_time[i][0]);
long long end_sec = hour_to_sec(log_time[i][1]);
time_table[start_sec]++;
time_table[end_sec]--;
}
for(int i=1; i<time_table.size(); i++)
time_table[i] += time_table[i-1];
for(int i=1; i<time_table.size(); i++)
time_table[i] += time_table[i-1];
long long pos = 0;
long long ad_time = hour_to_sec(adv_time_int);
long long max_v = time_table[ad_time - 1];
for(int i=0; i+ad_time<=time_table.size(); i++)
{
if(max_v < time_table[i+ad_time] - time_table[i])
{
pos = i+1;
max_v = time_table[i+ad_time] - time_table[i];
}
}
answer = sec_to_hour(pos);
return answer;
}처음에 문제를 어떻게 접근해야될지 감도 안잡혀서 힌트를 얻고 풀긴했는데, 접근법을 떠올리는게 어려웠던 문제였던 거 같다.
굳