[프로그래머스] 광고 삽입

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

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

 

누적합 또는 부분합을 이용하여 미리 계산된 배열을 가지고 시청자 누적 재생 시간이 가장 긴 구간을 찾는다.

경계선 이외에도 답이 될 수 있기 때문에 초마다 비교를 해주어야 했다.

'99:59:59' 를 초로 바꾸면 359999초 이다.

 

def solution(play_time, adv_time, logs):
    answer = 0
    section = [0] * 360001
    play_time = seconds(play_time)
    adv_time = seconds(adv_time)
    
    for i in logs:
        i = i.split('-')
        section[seconds(i[0])] = section[seconds(i[0])] + 1
        section[seconds(i[1])] = section[seconds(i[1])] - 1
    
    for i in range(play_time):
        section[i+1] = section[i+1] + section[i]
    
    for i in range(play_time):
        section[i+1] = section[i+1] + section[i]
    
    M = section[adv_time]
    
    for i in range(play_time):
        if i + adv_time > play_time:
            break
        else:
            if M < section[i+adv_time] - section[i]:
                M = section[i+adv_time] - section[i]
                answer = i + 1
    
    return seconds_rev(answer)

def seconds(time):
    h, m, s = time.split(':')
    
    return int(h) * 3600 + int(m) * 60 + int(s)

def seconds_rev(time):
    h = time // 3600
    m = (time % 3600) // 60
    s = time % 60
    
    return '{0:02d}:{1:02d}:{2:02d}'.format(h, m, s)
             
print(solution('02:03:55', '00:14:15', ['01:20:15-01:45:14', '00:40:31-01:00:00', '00:25:50-00:48:29', '01:30:59-01:53:29', '01:37:44-02:02:30'])) # 01:30:59