[프로그래머스] 광고 삽입 (2021 KAKAO Blind Recruitment)

문제 링크

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

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

 

풀이

개인적으로 엄청 헤맸던 문제입니다. 시간 0 ~ 360,000에 대해 시뮬레이션을 돌리면 쉽게 풀리는데, 그 생각을 못하고 재생 시작, 재생 끝나는 구간별로 처리하려다 보니 코드가 꼬여 시뮬레이션 방식으로 다시 풀게 되었습니다.

 

1) 모든 시간을 초 단위로 통일하는 게 편합니다.

2) 모든 log의 시작 시간, 끝 시간을 벡터에 담고 정렬해줍니다. 이때 시작 시간인지 끝 시간인지 확인할 수 있는 정보를 함께 넣습니다. (line 21~29)

3) 위에서 구한 벡터를 순회하며 어떤 시점에 몇 명이 재생을 시작하고, 끝내는지 저장해줍니다. 코드상에서 배열 d의 인덱스는 시간입니다. (line 36~42)

4) 모든 시간(0~360,000)에 대해 각 시점에 몇 명이 영상을 재생 중인지 구해줍니다. (line 44~46)

5) adv_time만큼의 구간 간격을 유지하며 각 구간의 누적 재생 시간을 비교해 최댓값과 가장 앞선 광고 시작 시간(정답)을 구해줍니다. (line 47~55)

 

정답 코드

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define ft first
#define sd second
using namespace std;
using pii = pair<int, int>;
using ll = long long;
using pll = pair<ll, ll>;

string foo(int s){
	int h = s/3600;
	s%=3600;
	int m = s/60;
	s%= 60;
	char ret[10];
	sprintf(ret, "%02d:%02d:%02d", h, m, s);
	return string(ret);
}

string solution(string play_time, string adv_time, vector<string> logs) {
	vector<pii> p;
	for(int i=0; i<logs.size(); i++){
		int h1, h2, m1, m2, s1, s2;
		sscanf(logs[i].c_str(), "%d:%d:%d-%d:%d:%d", &h1, &m1, &s1, &h2, &m2, &s2);
		
		p.emplace_back(h1*3600+m1*60+s1, 1);
		p.emplace_back(h2*3600+m2*60+s2, 0);
	}   
	sort(all(p));
	int h, m, s;
	sscanf(adv_time.c_str(), "%d:%d:%d", &h, &m, &s);
	int advTime = h*3600+m*60+s;
	sscanf(play_time.c_str(), "%d:%d:%d", &h, &m, &s);
	int playTime = h*3600+m*60+s;
 	   
	vector<int> d(400'000);
	for(pii now: p){
		auto [t, lr] = now;
		
		if(lr == 0) d[t]--;
		else d[t]++;
	}
	ll val = 0;
	for(int i=0; i<playTime; i++){
		d[i] += d[i-1];
	}
	for(int i=0; i<advTime; i++){
		val += d[i];
	}
	pll ans = {val, 0};
	
	for(int i=advTime; i < playTime; i++){
		val += d[i] - d[i-advTime];
		ans = max(ans, {val, -(i-advTime+1)});
	}
	
	return foo(-ans.sd);
}