2021 KAKAO BLIND RECRUITMENT - 광고 삽입

이 문제는 주어진 시간 단위를 초 단위로 바꿔서 푸는 것이 핵심이다. 시간이 최대 99:59:59까지 주어지는데, 이를 초단위로 바꾸면 359,999초이다. 이는 배열로 충분히 표현할 수 있는 크기이므로, 배열 logs에 주어진 각 구간들의 시작 시간과 끝 시간을 이용해 배열을 채워준 뒤, adv_time 크기의 구간합 중 최대값을 구해주면 된다.

 

문제를 풀기 위해 먼저 string 형으로 주어진 시간을 int 형 초로 바꾸는 함수와, 반대로 다시 문제에 주어진 포맷으로 바꾸는 함수를 만들었다.

 

int toInt(string time) { // string형 시간 -> int형 초
	int hour = stoi(time.substr(0, 2)) * 3600;
	int minute = stoi(time.substr(3, 2)) * 60;
	int second = stoi(time.substr(6, 2));
	return hour + minute + second;
}

 

string toTime(int sec) { // int형 초 -> string형 시간
	string hour = to_string(sec / 3600);
	if (sec / 3600 < 10) hour = "0" + hour;

	string minute = to_string((sec % 3600) / 60);
	if ((sec % 3600) / 60 < 10) minute = "0" + minute;

	string second = to_string(sec % 60);
	if (sec % 60 < 10) second = "0" + second;

	return hour + ":" + minute + ":" + second;
}

 

초 -> 시간으로 바꿀 때 시, 분, 초가 10보다 작다면 주어진 포맷에 맞추기 위해 앞에 0을 추가해준다.

 

이제 logs 배열을 순회하며 구간 시작 지점과 끝 지점을 초 단위로 바꾸고, 이를 인덱스로 해서 배열 preSum에 값을 채워준다(시작 지점은 +1, 끝 지점은 -1). 다 채운 뒤에는 아래와 같은 방식으로 누적합을 구해준다.

 

for (i = 1; i <= totLen; i++) { // prefix sum
	preSum[i] += preSum[i - 1];
}

 

이제 preSum 배열의 i=0에서 i=totLen-advLen까지 adv_time 크기의 구간을 차례대로 순회하며 최대값을 찾는다. 이때 주의할 점은 재생 기록이 00:00:00~99:59:59인 시청자가 최대 30만명까지 있을 수 있으므로, 최대값이 int형의 범위를 넘을 수 있다. 따라서 preSum 배열과 최대값을 저장하는 변수는 long long으로 선언해준다.

 

전체적인 코드는 아래와 같다.

 

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

using namespace std;

typedef long long ll;
const int MAX = 360001;
ll preSum[MAX];

int toInt(string time) {
	int hour = stoi(time.substr(0, 2)) * 3600;
	int minute = stoi(time.substr(3, 2)) * 60;
	int second = stoi(time.substr(6, 2));
	return hour + minute + second;
}

string toTime(int sec) {
	string hour = to_string(sec / 3600);
	if (sec / 3600 < 10) hour = "0" + hour;

	string minute = to_string((sec % 3600) / 60);
	if ((sec % 3600) / 60 < 10) minute = "0" + minute;

	string second = to_string(sec % 60);
	if (sec % 60 < 10) second = "0" + second;

	return hour + ":" + minute + ":" + second;
}

string solution(string play_time, string adv_time, vector<string> logs) {
	string answer = "";
	int i, j;
	int totLen = toInt(play_time), advLen = toInt(adv_time);
	for (auto it : logs) {
		string start = it.substr(0, 8), end = it.substr(9, 8);
		int sTime = toInt(start), eTime = toInt(end);
		preSum[sTime + 1]++;
		preSum[eTime + 1]--;
	}

	for (i = 1; i <= totLen; i++) { // 매 초마다 겹치는 구간의 수 구하기
		preSum[i] = preSum[i] + preSum[i - 1];
	}

	for (i = 1; i <= totLen; i++) { // prefix sum
		preSum[i] += preSum[i - 1];
	}

	ll maxa = 0;
	for (i = 0; i + advLen <= totLen; i++) {
		if (i == 0) {
			if (maxa < preSum[advLen]) {
				maxa = preSum[advLen];
				answer = toTime(i);
			}
		}
		else {
			if (maxa < preSum[i + advLen] - preSum[i]) {
				maxa = preSum[i + advLen] - preSum[i];
				answer = toTime(i);
			}
		}
	}
	return answer;
}