[카카오 2021] 광고 삽입

문제분석

"죠르디"의 동영상 재생시간 길이 play_time, 공익광고의 재생시간 길이 adv_time, 시청자들이 해당 동영상을 재생했던 구간 정보 logs가 매개변수로 주어질 때, 시청자들의 누적 재생시간이 가장 많이 나오는 곳에 공익광고를 삽입하려고 합니다. 이때, 공익광고가 들어갈 시작 시각을 구해서 return 하도록 solution 함수를 완성해주세요. 만약, 시청자들의 누적 재생시간이 가장 많은 곳이 여러 곳이라면, 그 중에서 가장 빠른 시작 시각을 return 하도록 합니다.

즉 전체 구간인 play_time에서 시청자 들이 시청한 시작,종료 지점이 logs에 저장되어있음.
adv_time 만큼 광고를 재생할때 최대한 많은 누적 시청시간 갖도록하는 광고의 시작시간 구하기.

시행착오

1. 문자열로 된 시간을 숫자로 바꾸기
2. logs를 시작,종료 순으로 정렬하고 시청자들의 시작 시간에 맞춰 adv_time만큼의 윈도우 움직이기.
3. 윈도우 안에 해당하는 다른 시청자의 시간을 합하여 최대 노출시간을 갖는 시작지점 찾기.

def change(h, m, s):
    return (h * 3600 + m * 60 + s)

def solution(play_time, adv_time, logs):
    h, m, s = map(int, play_time.split(':'))
    play_time = change(h, m, s)

    h, m, s = map(int, adv_time.split(':'))
    adv_time = change(h, m, s)
    
    temp = []
    for val in logs:
        s_t, e_t = val.split('-')
        h, m, s = map(int, s_t.split(':'))
        s_time = change(h, m, s)
        h, m, s = map(int, e_t.split(':'))
        e_time = change(h, m, s)
        temp.append((s_time, e_time))
    logs = temp
    
    logs.sort(key = lambda x : (x[0], x[1]))
    
    answer = 0
    
    length = len(logs)
    
    max_val = -(1e9)
    for i in range(length):
        s, e = logs[i]
        adv_end = s + adv_time
        if adv_end > play_time: continue
        
        sum_val = 0
        for j in range(i, length):
            s2, e2 = logs[j]
            if s2 > adv_end: break
            if adv_end > e2: sum_val += (e2 - s2)
            else :sum_val += (adv_end - s2)
        if sum_val > max_val:
            max_val = sum_val
            answer = s
    h = answer // 3600
    answer %= 3600
    h = str(h)
    
    m = answer // 60
    answer %= 60
    m = str(m)
    
    s = answer
    s = str(s)
    
    if len(h) == 1: h = "0" + h
    if len(m) == 1: m = "0" + m
    if len(s) == 1: s = "0" + s
        
    return (h + ":" + m + ":" + s)

문제점
1. 정답이 시청자의 시작시간에 있을것이란 보장이 없다.

위와 같은 상황에서 시청 시작시간은 90시간째인데. 90+50 은 100을 넘으므로 답 후보에 못들어가서 내 코드로는 답이 0:0:0 으로 나오게된다.
하지만 끝에 10시간을 포함하게 되는 50시간이 정답이다.
따라서 내 방식으로 해결하려면 시청시작 뿐 아니라 시청끝 시간도 고려해주어야한다.

2. 시간 복잡도가 너무 높다.
   logs는 30만 크기의 배열이다.
   내 코드의 시간복잡도는 시작 시간 개수 n * 뒤에 있는 시간 개수
   (n-1) + (n-2) + ... 1 이 되어 O(n^2). 수행 횟수 900억이 되며.
   1번에 따라 시청자의 종료시간까지 고려해주면 천억이 넘는 수행횟수를 갖게된다.

정답

카카오 공식 블로그를 통해 답을 확인하였다.

def change(h, m, s):
    return (h * 3600 + m * 60 + s)

def solution(play_time, adv_time, logs):
    #문자열을 숫자로 변경
    h, m, s = map(int, play_time.split(':'))
    play_time = change(h, m, s)

    h, m, s = map(int, adv_time.split(':'))
    adv_time = change(h, m, s)
    
    temp = []
    for val in logs:
        s_t, e_t = val.split('-')
        h, m, s = map(int, s_t.split(':'))
        s_time = change(h, m, s)
        h, m, s = map(int, e_t.split(':'))
        e_time = change(h, m, s)
        temp.append((s_time, e_time))
    logs = temp
    
    #play_time 만큼의 배열 도입해. 시청 시작, 시청 종료 시점 기록.
    visited = [0] * (play_time + 1)
    for s, e in logs:
        visited[s] += 1
        visited[e] -= 1
    
    #각 시점에 시청 중인 시청자 수 기록
    for i in range(1, play_time):
        visited[i] = visited[i] + visited[i-1]
    
    #0부터 해당시점까지의 누적시청자 수 기록
    for i in range(1, play_time):
        visited[i] = visited[i] + visited[i-1]

    most_view = 0
    max_time = 0
    for i in range(adv_time - 1, play_time):
        if i >= adv_time:
            if most_view < visited[i] - visited[i - adv_time]:
                most_view = visited[i] - visited[i - adv_time]
                max_time = i - adv_time + 1
        else:
            if most_view < visited[i]:
                most_view = visited[i]
                max_time = i - adv_time + 1
            
    answer = max_time
    h = answer // 3600
    answer %= 3600
    h = str(h)
    
    m = answer // 60
    answer %= 60
    m = str(m)
    
    s = answer
    s = str(s)
    
    if len(h) == 1: h = "0" + h
    if len(m) == 1: m = "0" + m
    if len(s) == 1: s = "0" + s
        
    return (h + ":" + m + ":" + s)

분석

1. 모든 문자열을 숫자로 변경
2. play_time 만큼의 배열 도입 후 시청자들의 시작지점에 +1을. 종료지점에 -1로 표시.
3. 이전 값을 현재 값에 더해줘 현 시점 시청자 수 표시.
   ex) 시작지점에 +1 해주고 종료지점에 -1 해주었으므로. 그 사이는 1이. 종료 후는 0이된다.
4. 이전 값을 현재 값에 한번 더 더해줘 현 시점 누적 시청자 수 표시.
   누적 시청자로 변경하지 않는다면 모든 구간에 대해 adv_time 만큼의 윈도우로 합을 구해야하기에 시간초과 발생한다.
5. 특정 구간의 adv_time 만큼의 시청자 수는 visited[i] - visited[i-adv_time]으로 구할 수 있다. 해당 값이 최대가 되는 i-adv_time을 구하면 됨.

구간의 시작, 종료 시점에 +1, -1 표시 후 누적합하여 구간 내부 값을 구하고.
누적합 후 뺄셈을 통해 구간 내부 합을 구할 수 있음.