광고삽입

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

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

처음 풀이: 이렇게 했더니 시간초과가 나고 틀렸다고 나온다. 시간 초과가 나온다는 것 자체가 다른 알고리즘을 요하는 것 같아서 누적합로 풀어야 함을 알게 되었다. 

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <sstream>
using namespace std;


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

bool cmp(pair<int,string>a, pair<int,string>b){
    return a.first > b.first;
}


string solution(string play_time, string adv_time, vector<string> logs) {
    string answer = "";
    sort(logs.begin(),logs.end());
    
    vector<int>logstart;
    vector<int> logend;
    vector<string>logstart_s;
 //   vector<string>logstart_e;
    
    int playtime = tosecond(play_time);
    int advtime = tosecond(adv_time);
    
    if(playtime == advtime){return "00:00:00";}
    
    for(int i=0; i<logs.size(); i++){
        string s = logs[i].substr(0,8);
        string e = logs[i].substr(9,8);
        
        int stime =tosecond(s);
        int etime = tosecond(e);
        
        logstart_s.push_back(s);
        
        logstart.push_back(stime);
        logend.push_back(etime);
     }
    
    
    
    vector<pair<int,string>> totalplaytime;
    
    //0초부터
    int playend = advtime;
    int totalplay =0;
     for(int i=0; i<logstart.size(); i++){
         if(playend<=logstart[i]){break;}
      if(logstart[i]<playend){
          if(logend[i]<=playend){
              totalplay+=(logend[i]-logstart[i]);
          }
          else if(logend[i]>playend){
              totalplay+=(playend-logstart[i]);
          }
      }
     }
    int maxtotal = totalplay;
    string maxtime = "00:00:00";

    //로그 시작시간 기준
    for(int i=0; i<logstart.size(); i++){
        int playend = logstart[i] + advtime;
        int totalplay =0;
       
        if(playend>playtime){playend=playtime;}

        for(int j=0; j<logstart.size(); j++){
            if(logend[j]<logstart[i]){continue;}
        
            if(logstart[j]<playend && logstart[j]>=logstart[i]){
               if(logend[j]<=playend){
              totalplay+=(logend[j]-logstart[j]);
                }
               else if(logend[j]>playend){
              totalplay+=(playend-logstart[j]);
                }
            }
            else if(logend[j]>logstart[i] && logstart[j]<playend){
               if(logend[j]>playend){
                 totalplay+=(playend-logstart[i]);  
               }
                else if(logend[j]<=playend){
                totalplay+=(logend[j]-logstart[i]);
 
                }
            }
        }
        if(maxtotal<totalplay){maxtotal = totalplay; maxtime = logstart_s[i];}
    }

  answer = maxtime;
    return answer;
}

 

누적합으로 풀었을 때

 

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <sstream>
using namespace std;


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



string solution(string play_time, string adv_time, vector<string> logs) {
    string answer = "";
//   sort(logs.begin(),logs.end());
    
    vector<int>logstart;
    vector<int> logend;
    
    int playtime = tosecond(play_time);
    int advtime = tosecond(adv_time);
    
   // if(playtime == advtime){return "00:00:00";}
    vector<int>totaltime(playtime+2,0);

    for(int i=0; i<logs.size(); i++){
        string s = logs[i].substr(0,8);
        string e = logs[i].substr(9,8);
        
        int stime =tosecond(s);
        int etime = tosecond(e);
        
        logstart.push_back(stime);
        logend.push_back(etime);

    }
    
    for(int i=0; i<logs.size(); i++){
        totaltime[logstart[i]]+=1;
        totaltime[logend[i]]-=1;
    }

    //totaltime[x] = 시각 x 부터 x+1까지 1초 간의 구간을 포함하는 재생 구간의 개수
    for(int i=1; i<=playtime; i++){ // 해당 구간에 몇명의 시청자가있는지 표현
       totaltime[i] += totaltime[i-1];
    }
    
    //totaltime[x] = 시각 0 부터 x+1까지 x+1초 간의 구간을 포함하는 누적 재생시간.
    for(int i=1; i<=playtime; i++){  // 해당 시간까지 총 누적 재생시간
       totaltime[i] += totaltime[i-1];
    }
    
    int max_time = totaltime[advtime-1];
    int maxstarttime =0;

    
    for(int i=0; i+advtime<=playtime; i++){
        int tmp = totaltime[i+advtime]-totaltime[i];//모든구간을 탐색하면서 최대값을 구한다. 
        
        if(tmp>max_time){
            max_time = tmp;
            maxstarttime = i+1;
        }
    }
    
    int hour = maxstarttime/3600;
    int minute = (maxstarttime/60)%60;
    int second = maxstarttime%60;
    
    string s_hour = to_string(hour);
    string s_minute = to_string(minute);
    string s_second = to_string(second);
    
    if(s_hour.size()==1){s_hour = "0"+s_hour;}
    if(s_minute.size()==1){s_minute = "0"+s_minute;}
    if(s_second.size()==1){s_second = "0"+s_second;} 
    
    answer = s_hour+":"+s_minute+":"+s_second;
    return answer;
}

주의 할 점: int -> long long 으로 바꿔야지 테케가 완벽하게 맞음!!

 

www.youtube.com/watch?v=idW6hlAiBO8 

 

<Java>

class Solution {
    
    public int toSecond(String time){
        
        int hour = Integer.parseInt(time.substring(0,2));
        int minute = Integer.parseInt(time.substring(3,5));
        int second =  Integer.parseInt(time.substring(6,8));
        return 60*60*hour+60*minute+second;
    }
    
    public String toTime(int num){
        
        String str ="";
        String hour =  Integer.toString(num/3600);

        String minute =  Integer.toString((num/60)%60);
        
        String second = Integer.toString(num%60);
        
        if(hour.length()==1){hour="0"+hour;}
        if(minute.length()==1){minute="0"+minute;}
        if(second.length()==1){second="0"+second;}

        return hour+":"+minute+":"+second;
    }
    
    
    public String solution(String play_time, String adv_time, String[] logs) {
        String answer = "";
        int playtime = toSecond(play_time);
        int advtime = toSecond(adv_time);
        long[]time = new long[playtime+1];
        
        for(int i=0; i<logs.length; i++){
           
            String str = logs[i];
            
            int start = toSecond(str.substring(0,8));
            int end = toSecond(str.substring(9,17));
            
            time[start]+=1; //동영상 시작시간에 1을 더해준다
            time[end]-=1; //동영상 끝나는 시간에 1을 빼준다
            
        }
        
        for(int i=1; i<=playtime; i++){
            time[i]+=time[i-1]; //누적합을 하고나면 time[i]는 i시간에 재생되는 동영상 수를 의미한다.
        }
        
        for(int i=1; i<=playtime; i++){
            time[i]+=time[i-1]; //누적합을 또하고나면 time[i]는 i시간까지 동영상 재생 시간을 의미하게 된다
        }
        
        int s =0; //광고 시작 시간
        int e = advtime; //광고 종료시간
        long max =time[e-1];  // 광고가 노출되는 시간이 최대일때
        int maxs =0; // 광고가 노출되는 시간이 최대일떄의 시작시간
        
        while(e<=playtime){ //광고 종료시간이 동영상 재생 끝을 넘지 않을 때까지 
             long total;
        
            total = time[e]-time[s]; //광고가 노출되는 시간 
           
            if(total>max){ //노출되는 시간이 최대일 때를 구한다.
                max = total;
                maxs=s+1;
            }
            
            s++;
            e++;
            
        }
        answer = toTime(maxs);
        
        
        return answer;
    }
}