문제 요약
동영상의 전체 재생 시간과 여러 시청자의 재생 구간이 주어진다.
정해진 길이의 광고를 동영상에 삽입할 때, 광고가 재생되는 구간의 누적 시청 시간이 최대가 되는 시작 시각을 구해야 한다.
누적 시청 시간이 같은 구간이 여러 개라면 가장 빠른 시작 시각을 반환한다.
시간은 다음 형식의 문자열로 주어진다.
HH:MM:SS핵심 아이디어
각 시청 기록의 모든 초를 직접 순회하면서 시청자 수를 증가시키면 재생 기록이 많을 때 매우 비효율적이다.
예를 들어 한 시청자가 다음 구간을 시청했다고 하자.
00:10:00-01:10:00이 구간의 3600초를 하나씩 증가시키는 대신, 시작 지점에는 +1, 종료 지점에는 -1만 기록한다.
시작 시각: +1
종료 시각: -1그다음 누적합을 한 번 계산하면 각 초에 동영상을 보고 있던 시청자 수를 구할 수 있다.
이를 차분 배열이라고 한다.
이후 누적합을 한 번 더 계산하면 특정 구간의 누적 시청 시간을 O(1)에 구할 수 있다.
전체 흐름은 다음과 같다.
시간 문자열을 초로 변환
차분 배열로 시청 시작과 종료 기록
첫 번째 누적합으로 초마다 시청자 수 계산
두 번째 누적합으로 누적 시청 시간 계산
모든 광고 시작 시각을 확인
최대 누적 시청 시간을 갖는 가장 빠른 시각 반환시간 문자열을 초로 변환하기
시간 계산을 문자열 상태로 처리하면 비교와 덧셈이 어렵다.
따라서 모든 시간을 초 단위 정수로 변환한다.
def to_seconds(time):
hour, minute, second = map(int, time.split(":"))
return hour * 3600 + minute * 60 + second예를 들어 다음 시간은,
01:30:59다음과 같이 계산된다.
1 × 3600 + 30 × 60 + 59
= 5459초초를 시간 문자열로 변환하기
정답은 다시 HH:MM:SS 형식으로 반환해야 한다.
def to_time(seconds):
hour = seconds // 3600
minute = (seconds % 3600) // 60
second = seconds % 60
return f"{hour:02d}:{minute:02d}:{second:02d}":02d는 숫자를 두 자리로 출력하고, 한 자리 숫자 앞에는 0을 붙인다.
1 -> 01
9 -> 09
12 -> 12재생 구간의 의미
재생 기록이 다음과 같다고 하자.
00:00:01-00:00:04이 시청자는 1초 이상 4초 미만인 구간을 시청한 것이다.
[1, 4)따라서 1초, 2초, 3초 구간에는 시청자가 포함되지만 4초부터는 포함되지 않는다.
차분 배열에는 다음과 같이 기록한다.
viewer_changes[start] += 1
viewer_changes[end] -= 1종료 시각에서 -1을 적용해야 재생 구간의 길이가 정확히 end - start가 된다.
첫 번째 누적합
차분 배열에는 시청자 수가 변하는 지점만 저장되어 있다.
누적합을 계산하면 각 초에 동영상을 시청 중인 사람의 수를 구할 수 있다.
for second in range(1, play_seconds):
viewer_changes[second] += viewer_changes[second - 1]계산이 끝난 뒤 viewer_changes[second]는 해당 1초 구간을 시청한 사람의 수를 의미한다.
예를 들어 값이 다음과 같다면,
viewer_changes[10] = 310초 이상 11초 미만의 구간을 시청한 사람이 3명이라는 뜻이다.
두 번째 누적합
각 초의 시청자 수를 구한 뒤 누적 시청 시간 배열을 만든다.
prefix = [0] * (play_seconds + 1)
for second in range(play_seconds):
prefix[second + 1] = (
prefix[second] + viewer_changes[second]
)prefix[t]는 0초부터 t초 직전까지의 누적 시청 시간을 의미한다.
따라서 start초부터 end초 직전까지의 누적 시청 시간은 다음과 같다.
prefix[end] - prefix[start]광고 길이가 adv_seconds라면 광고 시작 시각 start에 대한 누적 시청 시간은 다음과 같다.
end = start + adv_seconds
total = prefix[end] - prefix[start]풀이 과정
1. 전체 재생 시간과 광고 시간을 초로 변환
play_seconds = to_seconds(play_time)
adv_seconds = to_seconds(adv_time)2. 차분 배열 생성
동영상의 마지막 시각에도 종료 변화를 기록할 수 있도록 배열 크기를 play_seconds + 1로 만든다.
viewer_changes = [0] * (play_seconds + 1)3. 각 재생 기록 반영
재생 기록을 시작 시각과 종료 시각으로 나누고 초로 변환한다.
for log in logs:
start_text, end_text = log.split("-")
start = to_seconds(start_text)
end = to_seconds(end_text)
viewer_changes[start] += 1
viewer_changes[end] -= 14. 초마다 시청자 수 계산
차분 배열의 누적합을 계산한다.
for second in range(1, play_seconds):
viewer_changes[second] += viewer_changes[second - 1]5. 누적 시청 시간 계산
각 초의 시청자 수를 다시 누적한다.
prefix = [0] * (play_seconds + 1)
for second in range(play_seconds):
prefix[second + 1] = (
prefix[second] + viewer_changes[second]
)6. 첫 번째 광고 구간으로 초기화
광고가 0초에 시작하는 경우의 누적 시청 시간을 기준으로 잡는다.
best_start = 0
max_watch_time = prefix[adv_seconds]7. 모든 광고 시작 시각 확인
광고가 동영상 재생 시간을 벗어나지 않는 범위에서 시작 시각을 1초씩 이동한다.
for start in range(1, play_seconds - adv_seconds + 1):각 구간의 누적 시청 시간을 누적합으로 계산한다.
end = start + adv_seconds
watch_time = prefix[end] - prefix[start]기존 최댓값보다 클 때만 정답을 변경한다.
if watch_time > max_watch_time:같은 경우에는 갱신하지 않으므로 가장 빠른 시작 시각이 유지된다.
Python 코드
def solution(play_time, adv_time, logs):
def to_seconds(time):
hour, minute, second = map(int, time.split(":"))
return hour * 3600 + minute * 60 + second
def to_time(seconds):
hour = seconds // 3600
minute = (seconds % 3600) // 60
second = seconds % 60
return f"{hour:02d}:{minute:02d}:{second:02d}"
play_seconds = to_seconds(play_time)
adv_seconds = to_seconds(adv_time)
# 각 시각에서 발생하는 시청자 수의 변화를 저장한다.
viewer_changes = [0] * (play_seconds + 1)
for log in logs:
start_text, end_text = log.split("-")
start = to_seconds(start_text)
end = to_seconds(end_text)
viewer_changes[start] += 1
viewer_changes[end] -= 1
# 첫 번째 누적합: 각 초의 시청자 수를 구한다.
for second in range(1, play_seconds):
viewer_changes[second] += viewer_changes[second - 1]
# 두 번째 누적합: 0초부터 각 시각까지의 누적 시청 시간을 구한다.
prefix = [0] * (play_seconds + 1)
for second in range(play_seconds):
prefix[second + 1] = (
prefix[second] + viewer_changes[second]
)
best_start = 0
max_watch_time = prefix[adv_seconds]
# 광고를 시작할 수 있는 모든 시각을 확인한다.
for start in range(1, play_seconds - adv_seconds + 1):
end = start + adv_seconds
watch_time = prefix[end] - prefix[start]
# 같은 누적 시청 시간이면 더 빠른 기존 시각을 유지한다.
if watch_time > max_watch_time:
max_watch_time = watch_time
best_start = start
return to_time(best_start)코드 설명
차분 배열
viewer_changes[start] += 1
viewer_changes[end] -= 1한 시청 기록의 모든 초를 직접 증가시키지 않고 시청자가 들어오는 시각과 나가는 시각만 기록한다.
예를 들어 세 개의 로그가 각각 수천 초 길이라도 로그 하나당 두 번의 연산만 수행한다.
두 번의 누적합
첫 번째 누적합은 초마다 시청자 수를 구한다.
시청자 수의 변화 -> 각 초의 시청자 수두 번째 누적합은 특정 구간의 누적 시청 시간을 빠르게 계산하기 위해 사용한다.
각 초의 시청자 수 -> 시청 시간 누적합이 구조를 사용하면 광고 구간 하나의 누적 시청 시간을 O(1)에 계산할 수 있다.
광고 구간 계산
watch_time = prefix[end] - prefix[start]prefix[end]에는 0초부터 end초 직전까지의 누적 시청 시간이 들어 있다.
여기서 0초부터 start초 직전까지의 값을 빼면 광고가 재생되는 구간만 남는다.
가장 빠른 시각 유지
if watch_time > max_watch_time:비교 연산에 >=가 아니라 >를 사용한다.
시작 시각을 작은 값부터 순서대로 확인하므로 누적 시청 시간이 같을 때는 먼저 발견한 더 빠른 시각을 유지해야 한다.
큰 누적 시청 시간
동영상 길이보다 누적 시청 시간이 훨씬 커질 수 있다.
여러 시청자가 같은 구간을 동시에 시청하면 각 시청자의 시간이 모두 더해지기 때문이다.
파이썬의 정수는 필요한 크기에 맞게 자동으로 확장되므로 별도의 정수 범위 처리가 필요하지 않다.
예시
문제의 예시에서는 전체 재생 시간과 광고 시간이 다음과 같다.
play_time = "02:03:55"
adv_time = "00:14:15"시청 기록을 차분 배열에 반영하고 두 번의 누적합을 계산한 뒤, 광고 시작 시각을 0초부터 순서대로 확인한다.
가장 큰 누적 시청 시간을 만드는 광고 구간은 다음과 같다.
01:30:59부터 01:45:14까지따라서 반환값은 다음과 같다.
"01:30:59"시간 복잡도
동영상의 전체 길이를 초 단위로 T, 로그의 개수를 L이라고 하자.
각 로그를 차분 배열에 반영하는 데 다음 시간이 필요하다.
O(L)두 번의 누적합과 모든 광고 시작 시각 확인에는 다음 시간이 필요하다.
O(T)따라서 전체 시간 복잡도는 다음과 같다.
O(L + T)각 로그의 전체 재생 구간을 직접 순회하지 않기 때문에 효율적으로 처리할 수 있다.
공간 복잡도
초 단위 차분 배열과 누적합 배열을 사용한다.
O(T)정리
이 문제는 시간 구간을 차분 배열과 누적합으로 처리하는 문제다.
풀이 흐름은 다음과 같다.
HH:MM:SS 형식의 시간을 초로 변환
각 로그의 시작 시각에 +1, 종료 시각에 -1
첫 번째 누적합으로 초마다 시청자 수 계산
두 번째 누적합으로 구간 누적 시청 시간 계산
모든 광고 시작 시각을 순회하며 최댓값 탐색
동률이면 가장 빠른 시각 유지
정답을 HH:MM:SS 형식으로 변환각 시청 기록의 모든 초를 직접 처리하지 않고 시작과 종료 지점만 기록하는 것과, 누적합으로 광고 구간의 시청 시간을 O(1)에 계산하는 것이 핵심이다.
