코딩테스트 -- 광고 삽입 - (프로그래머스 / C++)

프로그래머스

 

문제!

---

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

"죠르디"의 동영상 재생시간 길이 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자리 문자열로 반환합니다.

---

요약하면 되도록 많은 시청자가 광고를 오래 시청하도록하는(누적 시청시간!) 시작시간을 구하는 문제!

 

처음에는 모든시간 00:00:01~ 99:59:59 까지 초단위의 배열을 만들어서 모든 시간에 대한 사용자의 수를 계산하려 했는데.

 

그렇게 되면 모든 배열의 수가 100*3600 = 360000 개... 감당이 불가능 할것 같아서 

다른 방법을 사용해 보기로 했습니다!

 

다음방법은 시작시간부터 광고 재생시간 까지를 모든 사용자와 비교해주는 방법을 생각해보았습니다

 

역시!  바로 실패...

#include <string>
#include <vector>
#include <algorithm>

#include <iostream>
using namespace std;

int ch_sec(string time){
    int sec=0;
    
    sec=stoi(time.substr(0,2))*3600+stoi(time.substr(3,2))*60+stoi(time.substr(6,2));
    
    return sec;
}

string ch_time(int time){
    string answer = "";
    
    if(time/3600<10){//시
        answer+="0"+to_string(time/3600)+":";
    }
    else{
        answer+=to_string(time/3600)+":";
    }
    time-=(time/3600)*3600;
    
    if(time/60<10){//분
        answer+="0"+to_string(time/60)+":";
    }
    else{
        answer+=to_string(time/60)+":";
    }
    
    time-=(time/60)*60;
    
    if(time<10){//초
        answer+="0"+to_string(time);
    }
    else{
        answer+=to_string(time);
    }
    
    return answer;
}

string solution(string play_time, string adv_time, vector<string> logs) {
    string answer = "";
    
    
    vector<vector<int>> memtime;//모든사람 시간
    vector<int>memo;
    vector<int> videoTime(360000, 0);

    int play=ch_sec(play_time);
    int ad= ch_sec(adv_time);
    
    int maxtime=0;
    
    
    if(play==ad){//같을때
        return "00:00:00";
    }
    
    
    for(string i : logs){//초단위로 모든사람 저장
        memo.push_back(ch_sec(i.substr(0,8)));
        memo.push_back(ch_sec(i.substr(9,8)));
        memtime.push_back(memo);
        memo.clear();
    }
    sort(memtime.begin(),memtime.end());
    
    
    for(int i=0;i<memtime.size();i++){
        videoTime[memtime[i][0]]+=1;
        videoTime[memtime[i][1]]-=1;
    }
    
    vector<int>start_ad(memtime.size());//누적시간 저장
    
    if(memtime[0][0]+ad>=play){// 첫번째 사람 시작때 광고를 재생했을때 -- > 플레이 타임을 넘김;;
        return ch_time(play-ad);
    }
    
    //겹치는 부분 계산
    
    int a=0;//첫
    int b=0;//끝
    
    for(int i=0;i<memtime.size();i++){//시작점에 광고재생
        a=memtime[i][0];
        b=memtime[i][0]+ad;
        
        for(int j=0;j<memtime.size();j++){
            if(b<memtime[j][0] and b<memtime[j][1]){//포함이 
                continue;
            }
            else if(a>memtime[j][0] and a>memtime[j][1]){//안되는 2가지 
                continue;
            }
            else{
                a=max(a,memtime[j][0]);
                b=min(b,memtime[j][1]);
            }
            start_ad[i]+=(b-a);//각 시작점 재생시 누적시간 계산
        }
        maxtime=max(maxtime,start_ad[i]);//최댓값 탐색
    }
    
    for(int i=0;i<start_ad.size();i++){
        if(start_ad[i]==maxtime){
            return ch_time(memtime[i][0]);
        }
    }
    
    // for(vector<int> i : memtime){// 출력
    //     cout<<ch_time(i[0])<<","<<ch_time(i[1])<<endl;
    // }
    
    return answer;
}

하면서도 누적시간의 최대가 항상 시작시간에 이루어지나...? 라는 의문이 들었었는데 끝까지 해보니 역시 안되네요;;

 

 

그렇게 다시 첫번째 방법! int list[ 360000 ]의 배열을 만들어 저장하는 방법을 사용해 보았습니다. 

 

다시 시작!

 

일단 현재 모든 시간이 99:59:59 을 초단위로 변환하는 함수

초단위를 99:59:59형식으로 변환해주는 함수를 만들어 줍시다.

int ch_sec(string time){
    int sec=0;
    
    sec=stoi(time.substr(0,2))*3600+stoi(time.substr(3,2))*60+stoi(time.substr(6,2));
    
    return sec;
}

string ch_time(int time){
    string answer = "";
    
    if(time/3600<10){//시
        answer+="0";
    }
    answer+=to_string(time/3600)+":";
    time-=(time/3600)*3600;
    
    if(time/60<10){//분
        answer+="0";
    }
    answer+=to_string(time/60)+":";
    time-=(time/60)*60;
    
    if(time<10){//초
        answer+="0";
    }
    answer+=to_string(time);
    
    return answer;
}

 

 

 

초단위를 저장할 배열과 플레이시간 광고시간을 선언해주고 

가장 기본적인 조건을 배제해줍시다.

    string answer = "";
    vector<int> all_time(360000, 0);

    int play=ch_sec(play_time);
    int ad= ch_sec(adv_time);
    
    if(play==ad){//같을때
        return "00:00:00";
    }

 

 

그리고 나서 모든 시청자의 시청시간을 배열에다 저장해줍시다.

이러면 배열에는 그 시간에 시청하고 있는 시청자의 수가 저장되게합니다.

    int start = 0;
    int end = 0;
    
    for(int i=0;i<logs.size();i++){//시간 초당 체크
        start=ch_sec(logs[i].substr(0,8));
        end=ch_sec(logs[i].substr(9,8));
        for(int j=start+1;j<=end;j++){// 모든 시간대에 시청자 기록
            all_time[j]++;
        }
    }

 

 

 

그러고 난 뒤 최대 누적시간을 가지는 부분을 찾는 부분

    long long a=0;//바로앞선 누적시간
    long long max=0;//현재최대치
    
    int time =1;
    for(int i=1;i<=(play-ad+1);i++){//계속 비교 1 ~ 광고를 시작할 수 있는 마지막지점 
        a+=(long long)(all_time[i+ad-1]-all_time[i-1]);//i초부터 i+광고 시간 까지의 누적 시청자의합
        if(a>max){//비교
            max=a;
            time=i;
        }
    }

모든 부분에서 광고를 시작해보고 그 광고가 재생되는동안의 누적 시청자(시간)합을 구해서

그의 최댓값을 구하고 그 시간 time을 출력해주면 끝!

 

 

 

ALL

#include <string>
#include <vector>

#include <iostream>
using namespace std;

int ch_sec(string time){
    int sec=0;
    
    sec=stoi(time.substr(0,2))*3600+stoi(time.substr(3,2))*60+stoi(time.substr(6,2));
    
    return sec;
}

string ch_time(int time){
    string answer = "";
    
    if(time/3600<10){//시
        answer+="0";
    }
    answer+=to_string(time/3600)+":";
    time-=(time/3600)*3600;
    
    if(time/60<10){//분
        answer+="0";
    }
    answer+=to_string(time/60)+":";
    time-=(time/60)*60;
    
    if(time<10){//초
        answer+="0";
    }
    answer+=to_string(time);
    
    return answer;
}

string solution(string play_time, string adv_time, vector<string> logs) {
    string answer = "";
    
    vector<int> all_time(360000, 0);

    int play=ch_sec(play_time);
    int ad= ch_sec(adv_time);
    
    if(play==ad){//같을때
        return "00:00:00";
    }
    
    int start = 0;
    int end = 0;
    
    for(int i=0;i<logs.size();i++){//시간 초당 체크
        start=ch_sec(logs[i].substr(0,8));
        end=ch_sec(logs[i].substr(9,8));
        for(int j=start+1;j<=end;j++){// 모든 시간대에 시청자 기록
            all_time[j]++;
        }
    }
    
    
    long long a=0;
    long long max=0;
    
    int time =1;
    
    for(int i=1;i<=(play-ad+1);i++){//계속 비교
        a+=(long long)(all_time[i+ad-1]-all_time[i-1]);//i초에 광고 시작시킨거
        if(a>max){
            max=a;
            time=i;
        }
    }
   
    answer=ch_time(time-1);
    return answer;
}

 

 

틀린점이 있다면 댓 달아주세요!