[프로그래머스 2021 KAKAO BLIND RECRUITMENT] 광고 삽입

문제

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

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

 

풀이

1. 시, 분, 초를 초로 변환한다면 배열을 사용해 구간의 누적 시간을 쉽게 관리할 수 있습니다. (v[i] = i ~ i +1초 누적시간) 

 

2. logs를 순회하며 보는 재생시간의 시작 점부터 끝 점까지 일일이 체크하여 1초씩 더해준다면 시간 초과가 나기때문에 일단은 시작 점에 +1, 끝 점에 -1을 체크해주고, 다 돌고나서 원래 v의 의미를 갖을 수 있도록 누적합을 더해가며 v[i]를 갱신해줍니다.

 

3. 길이가 k로 고정되어있으므로 슬라이딩 윈도우로 푸는 방법과 누적 합을 이용해 푸는 방법 두 가지을 생각해볼 수 있고, 아래는 두 방법의 구현 방법입니다.

---

•  슬라이딩 윈도우 

1. 시작 점과 끝 점을 s, e 라할 때, e - s 의 길이는 항상 k로 고정되며 s, e만 양의 방향으로 1씩 움직입니다.

 

2. 길이가 k인 구간 합을 관리하기 위해 첫 k개의 합인 v : [0, k - 1]의 합을 구하고, 위의 사진처럼 s, e를 진행함에 따라 추가되는 v[e]를 더해주고, 이전 구간의 첫 점인 v[s - 1]을 빼주며 최대 누적 구간을 찾아주면 됩니다.

 

•  누적 합

1. 길이가 k로 고정되어 있으므로 누적 합을 사용하기위해 v[i]의 개념을 v[i] = 0 ~ i + 1초까지 누적된 시간으로 바꿔서 생각할 수 있습니다. 따라서 v에 대해 누적합을 더해가며 한 번 더 갱신해야합니다.

 

2. 시작 점을 s라 할 때, 길이가 k인 합은 v를 누적된 시간으로 갱신했으므로 v[s + k - 1] - v[s - 1]으로 표현할 수 있고, 이에 가능한 s값까지 순회하며 최대 누적 구간을 찾아주면 됩니다. (s가 0인 경우 v[k - 1])

 

 

코드

* 슬라이딩 윈도우

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
ll v[360001];

int cal(string x) {
	int ret = 0;
	ret += ((x[0] - '0') * 10 + (x[1] - '0')) * 3600;
	ret += ((x[3] - '0') * 10 + (x[4] - '0')) * 60;
	ret += (x[6] - '0') * 10 + x[7] - '0';
	return ret;
}

string conv(int x) {
	string ret = to_string(x);
	if (x < 10) ret = '0' + ret;
	return ret;
}

string solution(string play_time, string adv_time, vector<string> logs) {
	int n = cal(play_time), k = cal(adv_time);
	for (string& S : logs) {
		int s = cal(S.substr(0, 8));
		int e = cal(S.substr(9));
		v[s]++; v[e]--;
	}
	
	for (int i = 1; i <= n; i++) v[i] += v[i - 1];
    
	int t = 0;
	ll Maxsum = 0, sum = 0;
    
	for (int i = 0; i < k; i++) sum += v[i];   
	Maxsum = sum;
    
	for (int e = k, s = 1; e <= n + 1; e++, s++) {
		sum += v[e] - v[s - 1];
		if (Maxsum < sum) {
			Maxsum = sum;
			t = s;
		}
	}
	return conv(t / 3600) + ":" + conv((t % 3600) / 60) + ":" + conv(t % 60);
}

 

* 누적 합 

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
ll v[360001];

int cal(string x) {
	int ret = 0;
	ret += ((x[0] - '0') * 10 + (x[1] - '0')) * 3600;
	ret += ((x[3] - '0') * 10 + (x[4] - '0')) * 60;
	ret += (x[6] - '0') * 10 + x[7] - '0';
	return ret;
}

string conv(int x) {
	string ret = to_string(x);
	if (x < 10) ret = '0' + ret;
	return ret;
}

string solution(string play_time, string adv_time, vector<string> logs) {
	int n = cal(play_time), k = cal(adv_time);
	for (string& S : logs) {
		int s = cal(S.substr(0, 8));
		int e = cal(S.substr(9));
		v[s]++; v[e]--;
	}
	
	for (int i = 1; i <= n; i++) v[i] += v[i - 1];
	for (int i = 1; i <= n; i++) v[i] += v[i - 1];
	
	int t = 0;
	ll Maxsum = 0, sum = 0;
	
	for (int s = 0; s + k - 1 <= n; s++) {
		if (s == 0) sum = v[k - 1];
		else sum = v[s + k - 1] - v[s - 1];
		if (Maxsum < sum) {
			Maxsum = sum;
			t = s;
		}
	}
	return conv(t / 3600) + ":" + conv((t % 3600) / 60) + ":" + conv(t % 60);
}