2021 KAKO BLIND RECRUITMENT [광고 삽입] [C++]

programmers.co.kr/learn/courses/30/lessons/72414

코딩테스트 연습 - 광고 삽입

---

문제요약

1.동영상의 재생시간, 광고 재생시간 , 사람들의 시청시간이 구간으로 주어진다

2.광고의 누적시청시간의 합이 최대가 되게 하는 광고삽입시각중을 출력한다

 

---

나의 풀이

예시로 나와있는 이러한 다이어그램을 보자마자 이건 1초씩 당기면서 시뮬레이션을 돌려서 알아내야 되겠다고 풀이전략을 생각했다.

 

특정 만약광고시간이 10분이고 1분부터 광고시작이 된다면  10분~11분 으로 광고가 나오게 될것이다

그리고 그 구간안에 있는 모든 사람들의 시청시간을 하나씩 count 해줘야 된다

 

광고 상영구간에 포함되어 있는 총 누적시간합계를 상수시간안에 구하지 못하면 시간복잡도가 초과할것같아서 누적합을 이용하여 특정구간의 누적시간합계를 전처리하였다

 

00:00:00 부터 끝까지 선형으로 광고시작시간을 1씩 올리면서 광고재생구간안에 광고시청시간의 합이 최대가 될때마다 update하는 방식으로 답을 계산한다.

---

풀이 과정

1. 시간을 기준으로 배열을 생성하고 배열안에 해당시간에 관람한 사람수를 초기화한다
2. 광고 범위는 고정이므로 1에서 생성한 배열을 누적합처리를 한다.
3. 00:00:00 부터 끝까지 사람들의 광고시청시간이 최대가 될때 광고시작시간을 update 하여 최종적으로 답을 출력한다.

---

느낀점

 

• 시,분,초 형식으로 나올때는 (초) 단위로 치환하여 시간을 표현하는게 좋은거같다.
• 문제를 풀기전 시간을 점으로 볼지 아니면 선분으로 봐야하는지 문제 예시를 보고 생각하는게 좋다 
• (예를 들어 1분부터 10분까지 광고재생시간이면 10분에 딱 들어온 사람도 포함을 해줘야 되는지 아닌지 예시를 보고 확인할것!)

---

코드

	#include <string>
	#include <vector>
	#include <cstring>
	#include <iostream>
	using namespace std;
	int getTimestamp(int h , int m , int s){
	return h*60*60+m*60+s;
	}
	string getHours(int ts){
	int h = ts/3600;
	string str = to_string(h);
	if(str.length()<2)str="0"+str;
	return str;
	}
	string getMinutes(int ts){
	int h = ts/3600;
	int m = (ts-h*3600)/60;
	string str = to_string(m);
	if(str.length()<2)str="0"+str;
	return str;
	}
	string getSeconds(int ts){
	int s = ts%60;
	string str = to_string(s);
	if(str.length()<2)str="0"+str;
	return str;
	}
	long long t[100*60*60+60*60+60];
	string solution(string play_time, string adv_time, vector<string> logs) {
	memset(t,0,sizeof(t));
	for (const string &log : logs){
	int h1 , h2 , m1 , m2 , s1 , s2;
	sscanf(log.c_str(),"%d:%d:%d-%d:%d:%d",&h1,&m1,&s1,&h2,&m2,&s2);
	t[getTimestamp(h1,m1,s1)]+=1;
	t[getTimestamp(h2,m2,s2)]-=1;
	}
	int h1 , h2 , m1 , m2 , s1 , s2;
	sscanf(play_time.c_str(),"%d:%d:%d",&h1,&m1,&s1);
	sscanf(adv_time.c_str(),"%d:%d:%d",&h2,&m2,&s2);
	int MAXTIME = getTimestamp(h1,m1,s1);
	int TAKETIME = getTimestamp(h2,m2,s2);
	int cur=0;
	for(int i=0;i<=MAXTIME;i++){
	cur+=t[i];
	t[i]=cur;
	}
	for(int i=1;i<=MAXTIME;i++){
	t[i]+=t[i-1];
	}
	long long maxTakeTime=0;
	int ans=0;
	for(int i=0;i+TAKETIME<=MAXTIME;i++){
	if(i==0){
	if(maxTakeTime<t[i-1+TAKETIME]){
	ans=i;
	maxTakeTime=t[i-1+TAKETIME];
	}
	}
	else{
	if(maxTakeTime<t[i-1+TAKETIME]-t[i-1]){
	ans=i;
	maxTakeTime=t[i-1+TAKETIME]-t[i-1];
	}
	}
	}
	return getHours(ans)+":"+getMinutes(ans)+":"+getSeconds(ans);
	}

view raw .cpp hosted with ❤ by GitHub