[programmers][2021카카오공채] 광고 삽입

문제 : programmers.co.kr/learn/courses/30/lessons/72414

---

부분합 문제.

hh:mm:ss 로 이루어진 문자열 시간으로는 계산하기 힘드므로 플레이타임, 광고시간, log 시간들 모두 second로 변환한 후 계산한다.

log의 시작 시간을 start, 종료 시간을 end라 한다면 subSum[start]++, subSum[end]-- 로 갱신한다.

예를 들어, start가 1, end가 3이라면

index (i)	0	1	2	3	4
subSum[i]	0	1	0	-1	0

모든 log 정보를 탐색하며 subSum을 갱신했다면 처음부터 모든 subSum을 탐색하며 subSum[i] = subSum[i] + subSum[i-1]로 정보를 갱신한다.

갱신하면 특정 시간대의 광고를 시청한 시청자 수가 구해진다.

index (i)	0	1	2	3	4
subSum[i]	0	1	1	0	0

우리는 누적 시청자 수를 구해야 하므로 한 번 더 subSum을 처음부터 탐색하며 갱신한다.

갱신하면 특정 시간대에 광고를 시청한 시청자의 누적 수가 구해진다. 

index (i)	0	1	2	3	4
subSum[i]	0	1	2	2	2

 

1~3의 시간대의 시청자의 수를 구하려면 subSum[3] - subSum[0(1-1)] = 2로 구할 수 있다.

위 수식을 사용하여 subSum을 앞에서 탐색하면서 탐색 중 최대 시청자 수인 경우 광고 시작 시간을 갱신시켜 나간다.

 

시간복잡도는 play_time을 초로 계산했을 때의 시간을 N이라 하면 O(N).

---

소스코드 : github.com/fpdjsns/Algorithm/blob/master/programmers/2021%EC%B9%B4%EC%B9%B4%EC%98%A4%EA%B3%B5%EC%B1%84/%EA%B4%91%EA%B3%A0%20%EC%82%BD%EC%9E%85.cpp

 

부분합의 범위는 int를 넘길 수 있다.