[프로그래머스] 광고 삽입 (Python, 2021 카카오 blind recruitment)

☁️ 문제 설명

• 시청자들이 가장 많이 보는 구간에 공익광고 넣기
• 시청자들이 해당 동영상의 어떤 구간을 재생했는지 알 수 있는 재생구간 기록을 구했고, 해당 기록으로 공익광고가 삽입될 최적의 위치를 고름
• 파란색: 동영상의 전체
• 검정색: 재생 기록을 구분하는 id
• 빨간색: 최적의 공익광고 위치 -> 이 구간을 시청한 시청자들의 누적 재생 시간이 가장 크기 때문

 

☁️ 입출력

• 입력
  • `play_time`: 동영상 총 재생 시간 길이 ("02:03:55")
  • `adv_time`: 공익광고의 재생시간 길이 ("00:14:15")
  • `logs`: 시청자들의 해당 동영상을 재생했던 구간 정보(["01:20:15-01:45:14", "00:40:31-01:00:00"])
• 출력
  • 공익광고가 들어갈 시작 시각 (여러 곳이면 가장 빠른 시각) ("01:30:59")

 

---

💡 풀이 아이디어

• 1. play_time, adv_time을 second로 변환
• 2. 차분 배열
• 3. 구간합: t초의 동시 시청자 수
• 4. 구간합: 누적 시청 시간
• 5. 슬라이딩 윈도우

 

💻 코드

def to_sec(hms):
    h, m, s = map(int, hms.split(':'))
    return h*3600 + m*60 +s

def to_hms(sec):
    h = sec // 3600
    sec %= 3600
    m = sec // 60
    s = sec % 60
    return f'{h:02d}:{m:02d}:{s:02d}'

def solution(play_time, adv_time, logs):
    p = to_sec(play_time)
    a = to_sec(adv_time)
    
    if a >= p:
        return '00:00:00'
    
    # 차분 배열
    diff = [0] * (p+2)
    
    for log in logs:
        s_str, e_str = log.split('-')
        s = to_sec(s_str)
        e = to_sec(e_str)
        diff[s] += 1
        diff[e] -= 1
    
    # 누적합: t초의 동시 시청자 수
    viewers = [0] * (p+1)
    cur = 0
    for t in range(p):
        cur += diff[t]
        viewers[t] = cur
        
    # 누적합: 누적 시청 시간
    sum = [0] * (p+1)
    for t in range(1, p+1):
        sum[t] = sum[t-1] + viewers[t-1]
    
    # 슬라이딩 윈도우
    best_start = 0
    best_sum = sum[a] - sum[0]
    
    for i in range(1, p-a+1):
        total = sum[i+a] - sum[i]
        if total > best_sum:
            best_sum = total
            best_start = i
    
    return to_hms(best_start)