[프로그래머스] 카카오 광고 삽입 c++

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

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

 

기본적인 아이디어.

 

최대시간 99:59:59는 359999초.

359999는 배열로 잡아도 메모리가 가능한 수준.

int time[i] = i ~ i+1초 동안 접속한 접속자 수

i초~ (i+광고시간)초 까지의 합이 최대인 구간을 구해 출력.

 

 

(주의)

광고시간, 동영상 재생시간 최대 99:59:59 = 359999초 

logs 배열의 최대크기 300,000

 

최대합 = 접속자 30만명(00:00:00~99:59:59) * 359999 = 107,999,700,000

int 범위가 넘어가므로

64비트 환경에서 정수형 범위 -9223372036854775808~9223372036854775807 를 지원하는

long을 쓰자

 

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

using namespace std;

int tosec(string s)
{
    int hh=(s[0]-'0')*10+s[1]-'0';
    int mm=(s[3]-'0')*10+s[4]-'0';
    int ss=(s[6]-'0')*10+s[7]-'0';
    
    return hh*3600+mm*60+ss;
}

string tostr(int i)
{
    
    string hh=to_string(i/3600);
    i=i%3600;
    if(hh.length()==1) hh="0"+hh;
    
    string mm=to_string(i/60);
    if(mm.length()==1) mm="0"+mm;
    
    string ss=to_string(i%60);
    if(ss.length()==1) ss="0"+ss;
    
    return hh+":"+mm+":"+ss;
}

//https://programmers.co.kr/learn/courses/30/lessons/72414
string solution(string play_time, string adv_time, vector<string> logs) {
    
    string answer = "";
    vector< vector <int> > myinout;
    vector< vector <int> > mylogs;
    int playt=tosec(play_time);
    int advt =tosec(adv_time);

    for(int i=0; i<logs.size(); i++)
    {
        vector <int> t1;
        vector <int> t2;
        
        t1.push_back(tosec(logs[i].substr(0,8)));
        t1.push_back(1);
        myinout.push_back(t1);
        
        t2.push_back(tosec(logs[i].substr(9)));
        t2.push_back(0);
        myinout.push_back(t2);
    }
    
    sort(myinout.begin(),myinout.end());
    
    int cnt=0;
    int temp;
    for(int i=0; i<myinout.size(); i++)
    {
        temp=myinout[i][0];
        
        for(i; i<myinout.size(); i++)
        {
            if(myinout[i][0]==temp)
            {
                if(myinout[i][1]==1) cnt++;
                else cnt--;
            }
            else
            {
                i--;
                break;
            }
        }
        
        vector <int> t;
        t.push_back(temp);
        t.push_back(cnt);
        mylogs.push_back(t);        
    }
    
   
    
    int tim[360001];
    long sum[360001];
    int j;   
    
    for(j=0; j<mylogs[0][0]; j++)
    {
        tim[j]=0;
    }
    
    for(int i=1; i<mylogs.size(); i++)
    {
        for(j; j<mylogs[i][0]; j++)
        {
            tim[j]=mylogs[i-1][1];
        }
    }    
    
    for(j; j<=playt; j++)
    {
        tim[j]=0;
        
    }
    
    sum[0]=0;
    for(int i=0; i<advt; i++)
    {
        sum[0]+=tim[i];
    }
 
    for(int i=1; i<=playt; i++)
    {
        if(i+advt>playt)break;
        sum[i]=sum[i-1]-tim[i-1]+tim[i+advt-1];
    }
    
    int mii=0;
    for(int i=1; i<=playt; i++)
    {
        if(i+advt>playt)break;
        if(sum[mii]<sum[i])
        {
            mii=i;
        }
    }
    
    
    
    answer=tostr(mii);
    
    return answer;
}

 

카카오 광고삽입 실행시간