문제 보기 · Level 3 · 2021 KAKAO BLIND RECRUITMENT · 정답률 37% · 푼 사람 5,638명 (2026-09-30 기준)1

문제

동영상 길이 play_time, 광고 길이 adv_time(둘 다 HH:MM:SS), 시청 기록 logs(H1:M1:S1-H2:M2:S2)가 주어진다. 광고를 동영상의 어느 시각에 시작해 끼워 넣을지 정한다. 광고가 나오는 동안 시청자들의 재생 시간을 모두 더한 값(누적 재생 시간)이 가장 큰 시작 시각을 HH:MM:SS로 돌려준다. 그런 곳이 여러 곳이면 가장 빠른 시각을 돌려준다. 재생 시간은 “끝 시각 − 시작 시각”이다. 1초부터 10초까지 봤다면 9초다.

  • 동영상·광고 길이 최대 99:59:59, 광고 ≤ 동영상
  • 기록 최대 300,000개

풀이

막히면 한 단계씩 펼친다.

필요한 개념
  • 시간·날짜 계산: HH:MM:SS를 초 하나로 바꾼다. 99:59:59는 359,999초다.
  • 누적 합과 차분 배열: 차분으로 “1초마다 보는 사람 수”를 만들고, 누적 합으로 “광고 구간의 합”을 뺄셈 한 번에 구한다.
  • 미적분의 기본정리: 누적 재생 시간은 “1초마다 보는 사람 수”를 광고 구간에서 적분한 값이다. 이 값이 누적 합 두 값의 차가 되는 것은 기본정리 2부(구간의 적분 = 끝값의 차)와 같은 모양이다.
1단계 · 작은 예로 손으로 풀기

동영상 10초, 광고 3초, 기록은 1~4초, 2~6초, 5~9초다. “i초 ~ i + 1초”를 한 칸으로 보고, 칸마다 보는 사람 수를 센다.

칸 0 1 2 3 4 5 6 7 8 9
보는 사람 0 1 2 2 1 2 1 1 1 0

광고를 t초에 시작하면 칸 t, t + 1, t + 2의 합이 누적 재생 시간이다. t = 0이면 3, t = 1이면 5, t = 2, 3도 5다. 가장 큰 값 5가 처음 나오는 t = 1, 곧 00:00:01이 답이다.

2단계 · 가장 단순한 방법과 그 속도

시작 시각 t마다 모든 기록과 겹치는 길이를 더한다. t는 최대 36만 가지, 기록은 30만 개라 약 1,000억 번이다. 기록마다 그 구간의 칸을 하나씩 +1 해도, 긴 기록 30만 개면 역시 1,000억 번 가까이 된다.

3단계 · 핵심 아이디어
  • 차분으로 보는 사람 수 만들기: 기록 s ~ e마다 cnt[s] += 1, cnt[e] −= 1만 적는다. 끝 시각 e의 칸은 보지 않으니 e에서 뺀다. 앞에서부터 누적하면 cnt[i]가 칸 i의 보는 사람 수가 된다.
  • 누적 합으로 구간 합 구하기: S[t]를 “칸 0 ~ t − 1의 합”으로 둔다. 광고를 t초에 시작하면 칸 t ~ t + A − 1을 덮으니 누적 재생 시간은 S[t + A] − S[t]다(A는 광고 길이). +1, −1 표시는 보는 사람 수의 차분이라 도함수 자리이고, 누적은 적분 자리다(합 ↔ 적분).
  • 시작 시각 모두 보기: t = 0 ~ P − A(P는 동영상 길이)를 보며 가장 큰 값을 고른다. 같은 값이면 먼저 나온 t를 남기려고 >로 비교한다.
4단계 · 코드 흐름
  1. 동영상 길이 P, 광고 길이 A를 초로 바꾼다.
  2. 길이 P + 1인 cnt에 기록마다 +1, −1을 적고 앞에서부터 누적한다.
  3. cnt를 한 번 더 누적해 S를 만든다(S[0] = 0).
  4. t = 0 ~ P − A에서 S[t + A] − S[t]가 가장 큰 첫 t를 찾아 HH:MM:SS로 바꾼다.
5단계 · 파이썬 코드 
def to_sec(t):
    h, m, s = map(int, t.split(":"))
    return h * 3600 + m * 60 + s

def solution(play_time, adv_time, logs):
    P, A = to_sec(play_time), to_sec(adv_time)
    cnt = [0] * (P + 1)
    for log in logs:
        s, e = log.split("-")
        cnt[to_sec(s)] += 1
        cnt[to_sec(e)] -= 1                  # 끝 시각의 1초는 보지 않는다
    for i in range(1, P + 1):                # cnt[i]: i초 ~ i+1초를 보는 사람 수
        cnt[i] += cnt[i - 1]
    S = [0] * (P + 1)                        # S[t]: 0초 ~ t초의 누적 재생 시간
    for i in range(P):
        S[i + 1] = S[i] + cnt[i]
    best, best_t = -1, 0
    for t in range(P - A + 1):
        v = S[t + A] - S[t]
        if v > best:                         # 같으면 앞의 것을 남긴다
            best, best_t = v, t
    return f"{best_t // 3600:02d}:{best_t % 3600 // 60:02d}:{best_t % 60:02d}"
  • map(int, t.split(":")): "01:30:59"를 ["01", "30", "59"]로 나눈 뒤 모두 정수로 바꾼다.
  • f"{x:02d}": 정수를 두 자리로, 모자라면 앞에 0을 붙여 쓴다. 7 → 07.
  • best_t % 3600 // 60: 한 시간을 넘는 부분을 버린 뒤 60으로 나눈 몫, 곧 분이다.
6단계 · 실행 추적

1단계의 예(P = 10, A = 3)

i 0 1 2 3 4 5 6 7 8 9 10
표시 cnt 0 1 1 0 −1 1 −1 0 0 −1 0
누적한 cnt 0 1 2 2 1 2 1 1 1 0 0
S[i] 0 0 1 3 5 6 8 9 10 11 11
t 0 1 2 3 4 5 6 7
S[t + 3] − S[t] 3 5 5 5 4 4 3 2

5가 처음 나오는 t = 1이 답이다. 문제의 예시 1도 같은 계산으로 01:30:59에서 36분(2,160초)이 나온다.

7단계 · 복잡도와 흔한 실수

기록 L개와 동영상 P초에 \(O(L + P)\)다. 기록 30만 개, 동영상 99:59:59로 재 보니 0.2초였다.

  • 끝 시각의 칸까지 보는 것으로 세어(cnt[e + 1]에서 빼기) 한 칸씩 어긋난다.
  • 같은 값에서 >=로 비교해 더 늦은 시각을 고른다.
  • 시작 시각을 P − A + 1개가 아니라 P − A개까지만 본다. 광고가 동영상 끝에 딱 맞게 끝나는 자리도 된다.
  • 답을 1:0:5처럼 0을 채우지 않고 쓴다.
검증: 문제의 예시 3개를 통과했고, 무작위 입력 1,500개에서 “시작 시각마다 기록과 겹치는 길이를 직접 더하는” 풀이와 결과가 같았다. 6단계의 두 표, 예시 1의 36분, 큰 입력의 시간도 확인했다 — 19_pg72414_p1.py

  1. 프로그래머스 스쿨, “광고 삽입” (https://school.programmers.co.kr/learn/courses/30/lessons/72414), 2026-09-30 조회. ↩