[PRO] 광고 삽입

1차원에서 누적합을 나중에 한번에 계산하게 하는 방법을 바로 떠올렸지만,
동영상 시청을 이상, 이하로 접근하여 삽질을 오래 했다.

아래는 이상, 이하로 접근했을 때의 풀이다. 정확도는 80.6점가 나온다.

def time_to_sec(time):
    h,m,s = map(int,time.split(":"))
    return h*60*60 + m*60 + s

def sec_to_time(sec):
    m,s = divmod(sec, 60)
    h,m = divmod(m, 60)
    return f"{h:02d}:{m:02d}:{s:02d}"

def solution(play_time, adv_time, logs):
    play_time_sec = time_to_sec(play_time)
    adv_time_sec = time_to_sec(adv_time)
    
    psum = [0]*(play_time_sec+2) # 누적합 한번에 처리하기 위한 리스트
    for log in logs:
        start, end = map(time_to_sec, log.split("-"))
        psum[start] += 1
        psum[end+1] -= 1
    
    
    for i in range(1, play_time_sec+1): # 누적합 계산
        psum[i] += psum[i-1]
    
    ans_adv_start_sec = 0
    max_sum = float('-inf')
    range_psum = [0] * (play_time_sec-adv_time_sec+1) # adv_psum[i]: i초 시각에 초 총합
    range_psum[0] = sum(psum[:adv_time_sec])
    
    for i in range(1, len(range_psum)):
        range_psum[i] = range_psum[i-1] - psum[i-1] + psum[i+adv_time_sec]
        if max_sum < range_psum[i]:
            ans_adv_start_sec = i
            max_sum = range_psum[i]
        
    
    return sec_to_time(ans_adv_start_sec)

시청시간을 이상, 이하가 아닌 이상, 미만으로 접근하여 다시 푼 코드는 다음과 같다. 처음에 이상, 이하로 접근하고 우당탕탕 바꾸는 과정이 매우 매끄럽지 못해서 다음에는 예시를 조금 더 잘 들어서 이용하는게 좋을 것 같다.

def time_to_sec(time):
    h,m,s = map(int,time.split(":"))
    return h*60*60 + m*60 + s


def sec_to_time(sec):
    m,s = divmod(sec, 60)
    h,m = divmod(m, 60)
    return f"{h:02d}:{m:02d}:{s:02d}"


def solution(play_time, adv_time, logs):
    play_time_sec = time_to_sec(play_time)
    adv_time_sec = time_to_sec(adv_time)
    
    psum = [0]*(play_time_sec+1) # 누적합 한번에 처리하기 위한 리스트
    for log in logs:
        start, end = map(time_to_sec, log.split("-"))
        psum[start] += 1 # 이상
        psum[end] -= 1 # 미만
    
    for i in range(1, play_time_sec): # 누적합 계산
        psum[i] += psum[i-1]
    
    ans_adv_start_sec = 0
    range_psum = [0] * (play_time_sec-adv_time_sec+1) # adv_psum[i]: i초 시각에 초 총합
    max_sum = range_psum[0] = sum(psum[:adv_time_sec-1])
    
    for i in range(1, len(range_psum)):
        range_psum[i] = range_psum[i-1] - psum[i-1] + psum[i+adv_time_sec-1]
        if max_sum < range_psum[i]:
            ans_adv_start_sec = i
            max_sum = range_psum[i]
    
    return sec_to_time(ans_adv_start_sec)

2022 카카오의 파괴되지 않은 건물은 위 누적합 개념을 2차원에 적용한다. 이러한 유형이 자주 등장하는걸로 보인다.