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

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

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

이 문제는 큐를 브루트 포스로 풀었을 경우 O(n^2)의 시간 복잡도를 가지며 시간초과가 발생한다. 처음 이 풀이를 사용하지 않았을 때 테스트케이스 마지막 3개는 시간초과로 통과하지 못하였다. 그렇기 때문에 O(n)의 시간복잡도를 가지는 풀이를 사용해야했다. 문제를 보면 시간은 ms단위가 없기 때문에 정수형으로 시간을 바꾸었을 때 생각보다 큰 숫자가 나오지 않는다. 우선 카카오에서 자주 출제되는 시간을 문자열로 주어지는 문제는 가장 작은 단위로 통일하여 시간을 계산해주는 것이 좋다. 나는 toint()라는 함수를 만들어 string을 초 단위의 정수형으로 변환하는 함수를 만들어 사용하였다. 코드는 아래와 같다.

#include <string>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>

using namespace std;

int arr[360000];

int toint(string str) { //문자열 시간을 정수형으로 변환
    int h = stoi(str.substr(0, 2));
    int m = stoi(str.substr(3, 2));
    int s = stoi(str.substr(6, 2));
    int ret = s;
    ret += (m * 60);
    ret += (h * 3600);
    return ret;
}

string tostr(int time) { //정수형 시간을 문자열로 변환
    string ret = "";
    int h = time / 3600;
    time %= 3600;
    int m = time / 60;
    time %= 60;
    int s = time;
    if(h < 10) //1자리일 경우 0 추가
        ret += '0';
    ret += to_string(h);
    ret += ":";
    if(m < 10) //1자리일 경우 0 추가
        ret += '0';
    ret += to_string(m);
    ret += ":";
    if(s < 10) //1자리일 경우 0 추가
        ret += '0';
    ret += to_string(s);
    
    return ret;
}

string solution(string play_time, string adv_time, vector<string> logs) {
    string answer = "";
    int adv = toint(adv_time); //광고 시간 정수형으로 변환
    int play = toint(play_time); //재생 시간 정수형으로 변환
    long long mnum = 0; //최대값 저장
    long long sum = 0; //현재 누적시간
    int idx = 0; //최대값의 시작시간 저장
    for(string str : logs) {
        int s = toint(str.substr(0, 8)); //시작시간
        int e = toint(str.substr(9)); //종료시간
        for(int i = s; i < e; i++) arr[i]++; //log들이 재생한 구간 표시
    }
    
    for(int i = 0; i < adv; i++) { //00:00:00부터 광고 시간만큼 재생한 수 계산
        sum += arr[i];
    }
    
    mnum = sum;
    
    for(int i = adv; i < play; i++) { //1초씩 늘려가며 
        sum -= arr[i - adv]; //1초 전 시청인원 빼기
        sum += arr[i]; //다음 1초 시청인원 추가
        if(mnum < sum) { //최대인 경우
            idx = i - adv + 1; //최대값에서의 시작 시간 저장
            mnum = sum; //최대값 갱신
        }
    }
    
    answer = tostr(idx); //최대값에서의 시작시간을 string으로 변환
    
    return answer;
}

이 문제는 광고 재생 시간이 일정하게 유지된다. 따라서 00:00:00초부터 종료시간까지 광고 시간이 슬라이딩하며 그 시간에 시청한 사람들의 수를 계산할 수 있다. 예를 들면 광고 재생 시간이 10초인 경우

 

 0초~9초 -> 1초~10초 -> 2초~11초 -> ...

 

이런 식으로 처음 시작 시간에 시청한 인원을 빼고 그 다음 초에 시청한 인원을 더하며 슬라이딩 방식을 사용한다면 O(n)만에 모든 시간에서 최대 인원이 시청한 시간을 알 수 있다. 하나를 빼고 하나를 더할 때마다 최대값인지를 확인하며 최대값인 경우 그때의 광고 시작 시간을 저장한다. 시작 시간은 정수형이기 때문에 마지막에 그 최대값을 문자열로 변환하여 리턴해주면 된다.

제출 결과

카카오에서 이런 문자열을 다루는 문제가 자주 나오기 때문에 문자열을 다루는 라이브러리 함수 특히 substr, stoi 등을 익혀놓는 것이 문제를 풀 때 상당히 도움이 된다.