Programmers. 광고 삽입

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

Programmers. 광고 삽입

문제 풀이

그리디나 이진 탐색이 아니라 누적합과 DP 문제였다. 누적합과 관련된 고난도 문제를 풀어보지 못해 아마 풀제되었어도 해결하지 못했을 것이다. 전체 필드의 길이는 30만초로 각 시청 기록들에 대해 시작 지점에 +1하고 끝나는 지점에 -1하여 시청자 상태를 기록한다. 그리고 1부터 누적합을 1번하면 각 시점 별 시청자가 나오고 다시 1번 더 수행하면 시청자가 누적합된 결과를 얻는다. 1번에 끝내지 않은 이유는 시작 지점에 시청을 하던 시청자가 중간에 끊고 그 중간에 또 다른 시청자가 시청하는 경우를 반영하지 못하기 때문이다. 2번 누적합을 하면 시청자의 수가 커질 수록 변동폭도 그만큼 커진다. 2번 누적합된 배열에 대해 start와 adv_sec + start 지점을 비교해 차이가 가장 큰 시점을 저장하여 변환한다. answer는 start + 1로 갱신하는데 total_time[end] - total_time[start] 는 start + 1에서 end까지의 누적 시청자를 의미하기 때문이다.

• 전체 영상 길이를 초 단위로 변환
• 영상 길이 + 1만큼의 배열 생성
• 광고 영상 길이를 초 단위로 변환
• 각 시청 기록마다 시작 시간, 종료 시간을 초로 변환하여 누적합 배열 좌표에 시청자 반영
• 누적합을 2번 수행
• 초기값은 0초 시작에 max_cnt는 total_time[adv_sec] - total_time[0]이다.
• 1부터 끝까지 순회하되 광고 종료 시각이 범위 밖이면 끝점으로 설정
• 매번 끝지점에서 시작지점을 빼 최댓값인지 검사 후 갱신
• 저장된 시각 변환하여 리턴

python 코드

def solution(play_time, adv_time, logs):
    def str_to_sec(strs):
        h, m, s = strs.split(":")
        return 3600 * int(h) + 60 * int(m) + int(s)
    def sec_to_str(nums):
        h = nums // 3600
        nums %= 3600
        m = nums // 60
        nums %= 60
        return ":".join([str(h).zfill(2) ,str(m).zfill(2), str(nums).zfill(2)])
    total = str_to_sec(play_time)
    adv_sec = str_to_sec(adv_time)
    total_time = [0 for _ in range(total + 1)]
    for log in logs:
        s, e = log.split("-")
        s_sec = str_to_sec(s)
        e_sec = str_to_sec(e)
        total_time[s_sec] += 1
        total_time[e_sec] -= 1
    for i in range(1, len(total_time)):
        total_time[i] = total_time[i] + total_time[i - 1]
    for i in range(1, len(total_time)):
        total_time[i] = total_time[i] + total_time[i - 1]
    max_cnt = total_time[adv_sec]
    answer = 0
    for start in range(1, total):
        end = total if start + adv_sec >= total else start + adv_sec
        if max_cnt < total_time[end] - total_time[start]:
            max_cnt = total_time[end] - total_time[start]
            answer = start + 1
    return sec_to_str(answer)