프로그래머스 - 광고 삽입 (C++)

Pixabay로부터 입수된 StockSnap님의 이미지 입니다.

 

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

프로그래머스

 이번 문제는 총 영상의 시간, 광고 시간, 죠르디의 재생 구간들이 주어질 때, 광고가 삽입될 최적의 시간을 구하는 문제이다. 이 문제를 처음 풀어봤었을 때, 어떻게 해야 할지 감이 잡히지 않았다. 그래서 다른 분들의 풀이를 참고하여 풀었었는데 시간이 지나도 그 풀이가 어렴풋이 먼저 생각이 났다. 그래서 그 풀이를 바탕으로, 나름대로 나의 생각을 더해 풀어 보았다.

 우선, 이 문제에서 구하는 것은 가장 광고를 많이 볼 시간대이다. 그리고 주어진 시간은 초까지 표시가 되어있다. 그렇기에 각 초마다 영상이 재생된 횟수를 기록한 후, 광고 시작 시간부터 광고 종료 시간까지의 재생 횟수 총합이 가장 큰 구간을 고르면 될 것이다. 그리고 주어진 값들의 타입은 문자열이기에 미리 주어진 문자열 시간들의 타입을 변경해줘야 한다. 이를 위한 대력적인 과정은 다음과 같다.

1. 주어진 값들을 숫자형(여기서는 long long)으로 바꾼다.
2. 주어진 logs의 시작 시간 + 1부터 종료 시간까지, 각 초마다 재생 횟수를 1씩 증가시키는 것으로 기록한다.
3. 광고 시작 시간에 따른 총 재생 횟수와 최대 재생 횟수를 선언한 후, 광고가 0초부터 시작했을 때의 총 재생 횟수를 기록한다.
4. 1초부터 총 영상 시간 - 광고 시간 + 1까지의 시간을 기준으로, 총 재생 횟수를 구한다. 그리고 최대 재생 횟수를 갱신할 수 있을 경우, 이를 갱신한다.

아래는 위의 절차를 구현한 코드이다. 아래의 코드에서 더 설명하고 싶은 부분들이 있다.

• StringToNum: 이 함수는 string 타입으로 주어진 시간을 long long 타입으로 변환하는 함수이다. ':'를 기준으로 string 시, string 분, string 초로 나눈 후, 1분은 60초이므로 분에는 60을 곱하고 1시간은 3600초이므로 시에는 3600을 곱한다. 그리고 이것들의 총 합을 반환한다.
• NumToString: 이 함수는 long long 타입으로 주어진 시간을 "02:03:55"와 같은 string 타입으로 변환하는 함수이다. 우선, 시간은 초단위 시간을 3600으로 나눈 몫이다.(1시간 = 3600초) 그리고 분은 시간을 뺀 값에서 60으로 나눈 값의 몫이며 분은 나머지 값이다.(1분 = 60초) 그리고 시간 + ":" + 분 + ":" + 초 형태로 반환하는데, 만약 시, 분, 초의 값이 10보다 작을 경우 그 값 앞에 '0'을 더함으로써 양식을 지킬 수 있게 했다.
• log의 반복문이 startTime + 1부터 시작하는 이유: 예제의 광고 시간은 01:30:59~01:45:14이다. 그리고 이 광고의 길이는 14분 15초이다. 즉, 광고 종료 시간 - 광고 시작 시간 = 광고 길이이다. 그리고, 만약 예제의 광고가 00:00:00부터 00:14:15까지 진행되든, 00:00:01부터 00:14:16까지 진행되든 광고의 길이는 14분 15초이다. 즉, 광고 길이에는 광고의 시작 시간은 포함되지 않는다. 광고 시작 시간 + 1부터 포함이 된다. 그렇기에 정확한 광고 재생 횟수를 위해서 log의 시작 시간 + 1부터 종료 시간까지 기록하였다.
• 광고 재생 횟수를 기록하는 첫 반복문이 for (int t = 1; t <= advTime; ++t)인 이유 (1부터 광고길이까지인 이유): 이 역시 위와 마찬가지로, 광고 시작 시간은 광고 길이에 포함되지 않기 때문이다. 그렇기에 첫 반복문은 광고가 00:00:00에서 시작할 때를 의미하는 것이기에 1부터 시작하였다.
• 반환할 때, return NumToString(advStartTime); 가 아니라 return NumToString(advStartTime - 1); 인 이유: 이 역시 마찬가지로 광고 시작 시간은 광고 길이에 포함되지 않는다. 그리고 반복문에서 최대 광고 재생 횟수를 갱신할 때, advStartTime = t;와 같이 시작 시간 + 1의 값을 저장한다. 그렇기에 답을 반환할 때에는 1을 뺀 값을 반환해야 한다.

#include <string>
#include <vector>

using namespace std;

long long StringToNum(string time)
{
    string strHour = time.substr(0, 2);
    string strMinute = time.substr(3, 2);
    string strSecond = time.substr(6);
    
    long long hour = stoll(strHour);
    long long minute = stoll(strMinute);
    long long second = stoll(strSecond);
    
    return hour * 3600 + minute * 60 + second;
}

string NumToString(long long time)
{
    string result = "";
    
    long long hour = time / 3600;
    time %= 3600;
    
    long long minute = time / 60;
    time %= 60;
    
    long long second = time;
    
    if (hour < 10)
        result = "0" + to_string(hour);
    else
        result += to_string(hour);
    result += ":";
    
    if (minute < 10)
        result += ("0" + to_string(minute));
    else
        result += to_string(minute);
    result += ":";
    
    if (second < 10)
        result += ("0" + to_string(second));
    else
        result += to_string(second);
    
    return result;
}

string solution(string play_time, string adv_time, vector<string> logs) {
    long long advStartTime = 1;
    
    long long playTime = StringToNum(play_time);
    long long advTime = StringToNum(adv_time);
    
    vector<int> playCheck(361000, 0);
    
    for (int i = 0; i < logs.size(); ++i)
    {
        string log = logs[i];
        
        long long startTime = StringToNum(log.substr(0, 8));
        long long endTime = StringToNum(log.substr(9));
        
        for (int t = startTime + 1; t <= endTime; ++t)
            ++playCheck[t];
    }
    
    long long curPlayCount = 0;
    long long maxPlayCount = 0;
    
    for (int t = 1; t <= advTime; ++t)
    {
        curPlayCount += playCheck[t];
        maxPlayCount += playCheck[t];
    }
    
    for (int t = 2; t <= playTime - advTime + 1; ++t)
    {
        curPlayCount -= playCheck[t - 1];
        curPlayCount += playCheck[t + advTime - 1];

        if (maxPlayCount < curPlayCount)
        {
            maxPlayCount = curPlayCount;
            advStartTime = t;
        }
    }
    
    return NumToString(advStartTime - 1);
}

 

---

참고했던 풀이

https://yabmoons.tistory.com/623