[Programmers] 광고 삽입

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/72414#

프로그래머스

슬라이딩 윈도우 기법을 이용하는 문제였습니다.

시스템 케이스 17번에서 거의 10초가 걸렸기 때문에 아슬아슬하게 통과한 코드입니다.

 

알고리즘은 아래와 같습니다.

1. 입출력 예 #2를 보면 01:00:00-11:00:00 : 해당 구간이 1회(2번 기록) 재생되었으므로 누적 재생시간은 10시간 00분 00초라고 주어집니다. 따라서, 주어진 광고의 범위는 사실상 [시작 시간 + 1초, 종료 시간]입니다.

2. 이 점을 유의하여 logs 벡터를 전 처리하여 arr 배열에 각 초마다 몇 개의 프로그램이 동시에 진행되고 있는지 기록합니다.

3. 슬라이딩 윈도우를 진행할 때 광고 삽입 시간을 업데이트하는 기준이 필요하므로 우선, [0초, ad_time초] 구간에서 광고가 총 몇 초동안 상영이 되는지 기록하고 answer를 "00:00:00"초로 지정합니다.

4. 1초씩 슬라이딩하면서 총 광고 상영시간을 체크하고 광고가 기존에 기록한 시간보다 더 오래 상영되었다면 answer를 업데이트합니다. (주의: 정답이 여러 개라면 가장 빠른 시간을 반환해야 하므로 반드시 기존에 기록한 시간보다 초과할 때만 업데이트합니다. 동등할 경우 업데이트 X)

5. 4번에서 구한 asnwer를 반환합니다.

 

	#include <string>
	#include <vector>
	#include <iostream>
	#include <algorithm>
	#include <climits>
	using namespace std;
	const int MAX = 360000;
	long long arr[MAX];
	int convertTimeToSeconds(string s)
	{
	int hour = stoi(s.substr(0, 2)) * 3600;
	int minute = stoi(s.substr(3, 2)) * 60;
	int second = stoi(s.substr(6, 2));
	return hour + minute + second;
	}
	string convertSecondsToTime(int time)
	{
	int hour = time / 3600;
	int minute = (time % 3600) / 60;
	int second = (time % 3600) % 60;
	string result = (hour < 10 ? "0" + to_string(hour) : to_string(hour))
	+ ":"
	+ (minute < 10 ? "0" + to_string(minute) : to_string(minute))
	+ ":"
	+ (second < 10 ? "0" + to_string(second) : to_string(second));
	return result;
	}
	string solution(string play_time, string adv_time, vector<string> logs) {
	if (play_time == adv_time)
	{
	return "00:00:00";
	}
	for (string log : logs)
	{
	string start = log.substr(0, 8);
	string end = log.substr(9, 8);
	int startTime = convertTimeToSeconds(start);
	int endTime = convertTimeToSeconds(end);
	for (int t = startTime + 1; t <= endTime; t++)
	{
	arr[t]++;
	}
	}
	string answer = convertSecondsToTime(0);
	int adTime = convertTimeToSeconds(adv_time);
	long long watchTime = 0;
	for (int t = 0; t <= adTime; t++)
	{
	watchTime += arr[t];
	}
	long long temp = watchTime;
	int maxTime = convertTimeToSeconds(play_time);
	for (int t = 1, t2 = adTime + 1; t2 <= maxTime; t++, t2++)
	{
	temp -= arr[t];
	temp += arr[t2];
	if (temp > watchTime)
	{
	answer = convertSecondsToTime(t);
	watchTime = temp;
	}
	}
	return answer;
	}

view raw .cpp hosted with ❤ by GitHub

 

개발환경: Programmers IDE

 

지적, 조언, 질문 환영합니다! 질문 남겨주세요~