title: "[프로그래머스] 광고 삽입 Python 파이썬 해설 (Level 3) - 이도훈"
cleanUrl: "programmers/72414"
description: "프로그래머스 Level 3 문제 [광고 삽입]의 풀이를 정리합니다."

문제 설명 및 제한사항

아이디어 및 해결 방법

코드

from bisect import bisect_left, bisect_right
from collections import defaultdict, namedtuple

Interval = namedtuple('Interval', ['start', 'end', 'weight'])

NOTHING, START, END = 0, 1, 2

def h2s(t):
    tokens = t.split(':')
    return 3600*int(tokens[0]) + 60*int(tokens[1]) + int(tokens[2])

def s2h(t):
    return f'{t//3600:02}:{(t%3600)//60:02}:{(t%3600)%60:02}'

def solution(play_time, adv_time, logs):
    if play_time == adv_time:
        return '00:00:00'
    
    # 시간 구간을 잘 조각내서, 그 안에 몇 개의 interval이 있는지 기록해둡니다.
    play_time, adv_time = h2s(play_time), h2s(adv_time)
    timepoints, candidate_intervals = [], []
    candidate_intervals.append((0, adv_time))
    
    for id, log in enumerate(logs, 1):
        start, end = log.split('-')
        start, end = h2s(start), h2s(end)
        
        timepoints.append((start, START, id))
        timepoints.append((end, END, id))
        timepoints.append((start + adv_time, NOTHING, id))
        timepoints.append((end - adv_time, NOTHING, id))
        
        candidate_intervals.append((start, start + adv_time))
        candidate_intervals.append((end - adv_time, end))
    
    timepoints.append((0, NOTHING, 0))
    timepoints.append((0 + adv_time, NOTHING, 0))
    timepoints.append((play_time - adv_time, NOTHING, 0))
    timepoints.append((play_time, NOTHING, 0))
    
    candidate_intervals.append((play_time - adv_time, play_time))
    
    timepoints = [(t, flag, id) for t, flag, id in timepoints if 0 <= t <= play_time]
    timepoints.sort()
    candidate_intervals = [(s, e) for s, e in candidate_intervals if 0 <= s and e <= play_time]
    candidate_intervals.sort()
    
    i, prev_t, nintervals, intervals = 1, 0, 0, []
    while i < len(timepoints):
        t, flag, id = timepoints[i]
        
        if t > prev_t:
            intervals.append( Interval(prev_t, t, (t-prev_t) * nintervals) )
            prev_t = t
            
        if flag == START:
            nintervals += 1
        elif flag == END:
            nintervals -= 1
            
        i += 1
    
    intervals.append( Interval(play_time, play_time, 0) )
    
    mx, answer = -1, 0
    lsum = 0
    l, r = 0, 0
    for adv_start, adv_end in candidate_intervals:
        
        while r < len(intervals):
            if intervals[r].start == adv_end:
                break
            lsum += intervals[r].weight
            r += 1
        
        while l < len(intervals):
            if intervals[l].start == adv_start:
                break
                
            lsum -= intervals[l].weight
            l += 1
            
        if lsum > mx:
            mx, answer = lsum, adv_start

    return s2h(answer)

출처

프로그래머스 코딩테스트 연습 https://school.programmers.co.kr/learn/challenges