프로그래머스 - 광고 삽입

광고 삽입

설명

"죠르디"의 동영상 재생시간 길이 play_time, 공익광고의 재생시간 길이 adv_time, 시청자들이 해당 동영상을 재생했던 구간 정보 logs가 매개변수로 주어질 때, 시청자들의 누적 재생시간이 가장 많이 나오는 곳에 공익광고를 삽입하려고 합니다. 이때, 공익광고가 들어갈 시작 시각을 구해서 return 하도록 solution 함수를 완성해주세요. 만약, 시청자들의 누적 재생시간이 가장 많은 곳이 여러 곳이라면, 그 중에서 가장 빠른 시작 시각을 return 하도록 합니다.

def getSecond(time):
    h = int(time[:2])
    m = int(time[3:5])
    s = int(time[6:8])
    return h*60*60 + m*60 + s

def solution(play_time, adv_time, logs):
    answer = ''
    totalPlay = getSecond(play_time)
    totalAd = getSecond(adv_time)
    timeline = [0]*(totalPlay+1)
    for log in logs:
        timeline[getSecond(log[:8])] += 1
        timeline[getSecond(log[-8:])] -= 1
    for i in range(1, len(timeline)): # 총 시청자
        timeline[i] += timeline[i-1]
    for i in range(1, len(timeline)): # 누적 시청자
        timeline[i] += timeline[i-1]
        
    maxWatch = 0
    for i in range(1, totalPlay-totalAd+1):
        partSum = timeline[i+totalAd-1]-timeline[i-1]
        if partSum > timeline[maxWatch+totalAd-1]-timeline[max(0, maxWatch-1)]:
            maxWatch = i
    

    answer = '{:02d}:{:02d}:{:02d}'.format(maxWatch//3600, maxWatch%3600//60, maxWatch%60)
    return answer

• 자 앞서서 헤맸던 누적합 문제이다. 한번 공부해봤으니 풀어보자
• 100시간은 대충 36만초 정도 됨 초로 변환하자.
• 우선 누적합을 위해 시청 시간이 시작되는 지점과 끝나는지점에 마킹한다.
• 그 다음 앞에서부터 차례대로 더해주면(누적합) 각 시청시간을 타임라인에 1씩 더한것과 동일해진다.
• 하지만 우리는 어떤 특정 시간에 사람이 제일 많이 봤는지가 궁금하다.
• 이를 위해서는 광고시간의 범위만큼 부분합을 또 확인해야 하는데, 이를 위해서 또 부분합을 쓰면 아주 빠르게 계산 가능하다.
• ex) 2~5초간 시청자 수 -> 5초까지의 시청자 수 - 1초까지의 시청자 수
• 그래서 누적합을 한번 더 돌리고, 광고시간 만큼의 범위에 대해서 계속해서 검사해준다.
• 가장 시청자가 많았던 시간이 answer