[Python] 프로그래머스 광고 삽입

1. 문제 - 프로그래머스 광고 삽입 (2021 카카오 기출)

https://school.programmers.co.kr/learn/courses/30/lessons/72414

 

💡알고리즘 - 누적합, 구간합 알고리즘

- 구간별 누적 재생시간을 구해야하는데, logs의 길이가 360,000 이므로 O(n^2)의 시간을 O(n)으로 줄여줄 만한 알고리즘을 사용해야한다.
- 이때 누적합의 배열을 구한 뒤, 해당 누적합 배열을 이용해서 구간합을 구함으로써 O(n) 의 시간으로 구간합을 구할 수 있는 알고리즘을 사용한다.

 

✍🏻 막힌 부분

- 처음에 단순히 2중 반복문으로 구간합을 구해서 풀었는데, logs가 10^5가 넘어가니 당연히 시간초과가 걸릴수밖에 없었다. 이부분을 어떻게 최적화할 수 있을지에서 막혔다.

 

✅ 풀이

def transform_time(time):  # 문자열로 저장된 시간은 문제별로 적절하게 시/분/초로 환산함으로써 계산을 쉽게 해야한다.
    hour, minute, second = map(int, time.split(":"))
    
    return 3600 * hour + 60 * minute + second

def reverse_time(time):    # 초를 시:분:초 문자열로 바꿔주는 함수
    h = time // 3600
    time %= 3600
    m = time // 60
    time %= 60
    s = time
    
    return f"{h:02d}:{m:02d}:{s:02d}"

def solution(play_time, adv_time, logs):
    if play_time == adv_time:
        return "00:00:00"
    play_time = transform_time(play_time)
    adv_time = transform_time(adv_time)
    
    timeline = [0] * (play_time + 1)   # 재생시간 마지막까지 처리 위해 인덱스 범위를 늘림

    # logs의 길이는 최대 360_000이기 때문에 O(n)에 해소하는 알고리즘을 적용해야함
    # prefix_sum (구간합) 알고리즘 활용
    for log in logs:
        start, end = log.split("-")
        start_sec = transform_time(start)
        end_sec = transform_time(end)
        timeline[start_sec] += 1
        timeline[end_sec] -= 1

    # 누적합1: 시간별 누적 시청자 수
    for i in range(1, play_time + 1):
        timeline[i] += timeline[i - 1]

    # 누적합2: 시각별 누적 재생시간
    for i in range(1, play_time + 1):
        timeline[i] += timeline[i - 1]

    max_time = 0
    answer = 0
    
    for start in range(play_time - adv_time + 1):
        end = start + adv_time
        prefix_sum = timeline[end - 1] - timeline[start - 1]
        if prefix_sum > max_time:
            max_time = prefix_sum
            answer = start

    return reverse_time(answer)

 

1) 누적합1: 시간별 시청자수를 구한다.

logs의 각 start 지점에는 시청자가 있으니 + 1을 해주고, end 지점에는 시청자가 없으니 이후 누적합 적용을 위해 -1 을 해준다.

(아래 코드 대체

        for t in range(start, end+1):
            arr[t] += 1)

    timeline = [0] * (play_time + 1)   # 재생시간 마지막까지 처리 위해 인덱스 범위를 늘림

    # logs의 길이는 최대 360_000이기 때문에 O(n)에 해소하는 알고리즘을 적용해야함
    # prefix_sum (구간합) 알고리즘 활용
    for log in logs:
        start, end = log.split("-")
        start_sec = transform_time(start)
        end_sec = transform_time(end)
        timeline[start_sec] += 1
        timeline[end_sec] -= 1

    # 누적합1: 시간별 누적 시청자 수
    for i in range(1, play_time + 1):
        timeline[i] += timeline[i - 1]

 

2) 누적합2: 시간별 누적 재생 시간 구하기

위에서 한번 더 누적시킴으로써 구간별 총 재생시간을 구한다.

(sum(arr[start: start + adv_time + 1) 대체)

    # 누적합2: 시각별 누적 재생시간
    for i in range(1, play_time + 1):
        timeline[i] += timeline[i - 1]

 

3) 시간 비교하며 최대값 구하기

영상을 넣을 수 있는 가장 마지막 시작점인 play_time (영상 재생시간) - 광고 재생시간까지 순회하며,

start부터 start + adv_time(광고가 끝나는 지점) 의 구간합 (timeline[end - 1]  - time[start - 1])을 비교한다.

    max_time = 0
    answer = 0
    
    for start in range(play_time - adv_time + 1):
        end = start + adv_time
        prefix_sum = timeline[end - 1] - timeline[start - 1]
        if prefix_sum > max_time:
            max_time = prefix_sum
            answer = start

    return reverse_time(answer)

 

* 여기서 timeline[end] - timeline[start - 1] 가 아니라 timeline[end - 1] - timeline[start - 1]인 이유가 헷갈렸는데,

예를들어 10초부터 시작하는 5초짜리 공익 광고라고 가정하면 10 ~ 14초까지의 누적 재생시간을 구해야한다. (15초는 포함 X)

따라서 end에서 1 빼주어야한다.