1. 문제 설명

광고 삽입

2. 문제 분석

투-포인터 문제로 특정 '구간'에 해당하는 총합을 유도하는 문제이다. 뒤의 인덱스가 앞의 인덱스를 사용한 배열을 이용한다는 점에서 dp이기도 하다. 문제를 분석하면 다음과 같다.

1. 영상 범위 play에 광고 시간 adv를 삽입해야 한다. 사람들이 시청한 logs 기록에 따라 광고를 삽입한다. 광고 타깃은 '이 구간을 본 사람들의 총합'이 최대인 경우이다.
2. logs를 통해 특정 사람이 시청한 구간을 구할 수 있다.
3. 특정 '시점'을 총 몇 명이 본 지 구할 수 있다.
4. 특정 '구간'을 총 몇 명이 본 지 구할 수 있다.
5. 시청자 총합이 가장 큰 구간을 구한 뒤, 이 구간이 시작하는 '시점'을 return한다.

• start, end point에 각각 +1, -1을 '미리'함으로써 dp를 사용하는 데 준비해두자. sum(times[i:i+adv])이 이동할 때-즉 광고 구간을 앞에서부터 1초씩 뒤로 움직일 때-, adv-i부분을 고려하지 않으므로 이를 '미리' 빼고, 다음 부분 i를 '미리' 더하는 과정을 통해 sum을 여러 번 할 필요가 없다. 만일 sum을 남발한다면 시간 초과가 발생할 터이다.

3. 나의 풀이

def solution(play_time, adv_time, logs):

    def to_second(time):
        h, m, s = map(int, time.split(':'))
        return h * 3600 + m * 60 + s
    def to_time(second):
        h, rest = divmod(second, 3600)
        m, s = divmod(rest, 60)
        time = f'{h:02}:{m:02}:{s:02}'
        return time
    # 시간(문자열)을 초(정수)로, 초(정수)를 시간(문자열)로 변환

    play = to_second(play_time)
    adv = to_second(adv_time)

    times = [0]*(play+1)
    # 초 단위로 나뉜 '전체 범위'. 이 '초'의 구간을 몇 명이 보고 있는가?

    logs.sort()
    for log in logs:
        start, end = log.split('-')
        start = to_second(start)
        end = to_second(end)
        times[start] += 1
        times[end] -= 1
        # start~end 초까지 보고 있으므로 1명 추가. end초부터는 보지 않으므로 1명 미리 빼준다(two-pointer 사용하므로).
    
    start = to_second(logs[0].split('-')[0])
    # 0명부터 시작하므로.
    for i in range(start+1, play+1):
        times[i] += times[i-1]
        # for 문이 끝난 뒤 times[point]는 각 point 당 보고 있는 사람들의 수를 담고 있다.
        
    cur_time = sum(times[:adv])
    max_time = cur_time
    max_idx = 0
    # 광고 구간을 보는 사람들의 총합을 카운트. max 값이 바뀌어야 시작 구간이 바뀐다.

    for i in range(adv, play+1):
        cur_time += times[i]
        cur_time -= times[i-adv]
        # 광고 구간이 이동하면 지나간 부분(idx:i-adv)은 빼주고 오는 부분(idx:i)을 더해주면 사람 수가 구해진다.
        if max_time < cur_time:
            max_time = cur_time
            max_idx = i-adv + 1

    return to_time(max_idx)

• two-pointer 문제는 매우 중요하다. Lv3 문제에서 각종 유형에서 익숙해질 수 있도록 노력하자.