[프로그래머스/C++] 광고 삽입

 

 

문제

문제 설명

 

 

 

풀이

 

[문제 풀이]

 

처음 이 문제를 봤을 때, 요격 시스템 과 비슷한 문제인 줄 알았다...

 

그렇게 별 생각 없이 문제를 풀려고 했더니 전혀 다른 문제라는 것을 알게 됐다.

 

이 문제는 광고는 길이가 포함되어 있기 때문에, 실제로 광고를 시청한 시간이 가장 긴 부분을 계산해야 됐기 때문이다.

 

그래서 어떻게 문제를 풀까? 고민을 하다가 어차피 특정 구간에 광고를 시청했는지 파악을 하려면 누적합을 이용하면 총 [3600*100(시간) - 광고길이] 만큼만 크기 비교를 하면 되니까 풀리겠다는 생각이 들었다.

 

문제는 여기서도 고민이 생겼다.

 

누적합으로 문제를 해결하는 것은 어렵지 않은데, 누적합을 구하기 위해 특정 구간에 몇명이 광고를 보고 있는지 표시를 해야했다.

 

영상을 보는 사람의 수가 300000이므로, 사람이 들어올 때 마다, 구간에 1을 더한다면 최악의 경우 300000*3600*100만큼 덧셈 연산을 해야하기 때문이다.

 

그래서 고민 끝에 사람이 들어올 때 마다 더하는게 아니라 어떤 사람이 어느 시점부터 영상을 보기 시작했는지만 표시하고, 그 뒤에 영상의 시간만큼 for문을 돌려 특정 지점에는 몇명이 영상을 보고 있는지 표시하는 방법을 생각했다.

 

처음에는 정렬을 사용해 문제를 해결했다.

아래 그림과 같이 시청구간이 있다고 가정하자.

그러면 -1이 표시된 구간은 이전에 나온 -1이 아닌 값중 가장 최신 값들로 전부 변경을 해주면 된다.

문제는 정렬에 걸리는 시간이다.

정렬은 O(NlogN)의 시간복잡도를 갖기 때문에 정렬에 시간이 오래 걸렸다.

 

[두번째 방법]

그러다가 더 나은 방법이 생각 났는데, 사람이 빠지고 들어가는 부분을 1과 -1로 표시를 해 증가량을 나타낸 다음 앞에서 부터 더하는 방법이었다.

 

(첫 방법은 사람의 인원을 직접! 표시하는 방법이고, 두번째 방법은 사람의 증가량을 표시하는 방법이다.)

이렇게 각 구간에 영상을 보는 사람의 인원을 표시하고, 구간의 누적합을 구했다.

 

이후 최댓값을 구하기 위해 for문으로 배열을 탐색하면서 [시청지점+광고길이] - [시청지점]의 최댓값을 구하고, 언제 시청하는게 가장 많은 시간동안 광고를 보는지 return했다.

 

​

[아이디어 정리]

1. 영상을 시청하는 사람들의 증가량을 표시한다.
2. 증가량을 앞에서부터 더해 실제 구간에는 몇 명이 광고를 시청하는지 구한다.
3. 누적합을 구한다음 for문을 돌려 광고 시청시간의 최댓값이 되는 시작 지점을 구한다.

+ 문자로 나타난 시간들은 substr함수를 이용해 잘 구분하고 전부 초로 변환해 숫자로 비교했다.

 

 

 

Code

 

 

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int getTime(string str)
{
    int h,m,s;
    h=stoi(str.substr(0,2))*3600; 
    m=stoi(str.substr(3,5))*60;
    s=stoi(str.substr(6,8));
    return h+m+s;

}
string solution(string play_time, string adv_time, vector<string> logs) {
    string answer = "";
    vector<long long> time(getTime(play_time)+1,0);
    vector<pair<int,bool>> sortTime(logs.size()*2);
    time[0]=0;
    
    for (int i=0; i<logs.size(); i++)
    {
        time[getTime(logs[i].substr(0,8))]+=1;
        time[getTime(logs[i].substr(9,17))]-=1;        
    }
    int nowT=time[0];
    vector<long long> nT(time.size()+1,0);
    for (int i=1; i<time.size(); i++)
    {
        nowT+=time[i];
        nT[i+1]+=nT[i]+nowT;
    }
    long long maxV=0;
    int stTime=0;
    int ttt=getTime(adv_time);
    for (int i=ttt; i<nT.size(); i++)
    {        
        if (maxV<nT[i]-nT[i-ttt])
        {
            maxV=nT[i]-nT[i-ttt];
            stTime=i-ttt;
        }
    }
    int h,m,s;
    h=stTime/3600, stTime%=3600;
    m=stTime/60, stTime%=60;
    s=stTime;
    if (h<10)
        answer+="0";
    answer+=to_string(h)+":";
    if (m<10)
        answer+="0";
    answer+=to_string(m)+":";
    if (s<10)
        answer+="0";
    answer+=to_string(s);
    return answer;
}

 

---

처음에 시간 복잡도 때문에 고민을 많이 했는데, 실제로 그냥 st ~ ed 구간을 1씩 전부 더하면서 푼 풀이도 있었다

궁금해서 그 코드를 실행해보니 확실히 시간차이가 많이 났다;;

생각보다 쉬운 문제였는데, 풀때는 정말 어렵게 느껴졌다. 머리가 굳어버렸나... 

 

프로그래머스