[프로그래머스-파이썬] 광고 삽입

https://school.programmers.co.kr/learn/courses/30/lessons/72414

 

이 문제는 나와있는 모든 수를 초로 바꿔서 생각해야한다.

 

watch : 시청자가 시청을 시작하면 +1 시청을 끝내면 -1을 두고 이걸 누적합으로 계속 계산해오면 해당 인덱스에 총 시청자 수를 알 수 있다.

(이 부분을 첨에 무식하게 시청자 시작부터 끝까지 모든 인덱스에 +1로 해서 O(n^2)이 되었었다.)

 

dp : 그 다음 시청자 정보를 기반으로 누적 시청자를 계산한다. why? 구간 합을 구하기 위해서이다. 슬라이딩 윈도우에서 윈도우 크기가 동일하기 때문에 누적합에서 현재 - 시작을 빼면 구간합이 된다. 계속 윈도우를 밀어가면서 조건에 충족하면 시작시간을 업데이트 해준다.

 

def change_time(time):
    time = time.split(':')
    time = int(time[0]) * 3600 + int(time[1])*60 + int(time[2])
    return time

def covert_sec(time):
    hours = time // 3600
    left_sec = time % 3600
    minute = left_sec // 60
    second = left_sec % 60
    return f"{hours:02}:{minute:02}:{second:02}"

def solution(play_time, adv_time, logs):
    answer = ''
    
    if play_time == adv_time:
        return '00:00:00'
    
    play = change_time(play_time)
    adv = change_time(adv_time)
    log = [[change_time(t) for t in l.split('-')] for l in logs]

    dp = [0]*(play+1)
    watch = [0]*(play+1)
    
    for s, e in log:
        watch[s] += 1
        watch[e] -= 1
        
    for t in range(1, play):
        watch[t] += watch[t-1]
        
    dp[0] = watch[0]
    for i in range(1, play):
        dp[i] = dp[i-1] + watch[i]
    
    max_time = dp[adv-1]
    start_time = 0
    
    for i in range(adv, play):
        now = dp[i] - dp[i-adv]
        
        if now > max_time:
            max_time = now
            start_time = i-adv+1
    answer = covert_sec(start_time)
    return answer