광고 삽입 (2021 카카오 기출)

https://programmers.co.kr/learn/courses/30/lessons/72414?language=python3 

코딩테스트 연습 - 광고 삽입

 

일단 내가 문제를 처음 보고 떠올린 아이디어는

1. 초로 환산해야 한다.

2. 매 초마다의 동시 재생 수를 구해야 한다.

3. sliding window로 누적 재생 시간을 계산하며 최적의 시작 지점을 찾는다.

였다.

 

내가 지금 피시방이라 코딩하기가 좀 힘든 환경이어서 아이디어를 떠올린 뒤에 그냥 바로 해설을 읽어봤다. (어차피 정답률 1%문제라서 내가 혼자 풀 수 있을거란 자신감도 없었다..ㅋㅋㅋ)

 

해설도 매 초마다 뭔가를 작업한다는 아이디어는 나랑 공통적이었다. 근데 저걸 좀 더 영리하게 했다. 약간 적분하는 느낌?? (나중에 다시 생각해봤는데 이렇게 하지 않으면 절대 문제를 효율적으로 풀지 못한다.. 대체 이런발상은 어떻게한거야;;; 오늘도 자괴감up!!)

1. total_time[x] = x 시각에 시작된 재생 구간의 개수 – x 시각에 종료된 재생구간의 개수

logs를 순회하며 기록하면 된다.

뭐 [1,1,1,1,-1,-1,-1,-1]

[2,0,-1,3,-1,-2,-1,0]

이런식으로 나오겠지

2. total_time[i] = total_time[i] + total_time[i - 1]

이렇게 전 요소를 후 요소에다 더해주면 그 초에 동시 재생 수가 된다.

[1,1,1,1,-1,-1,-1,-1]를 예로들면

[1,2,3,4,3,2,1,0]이 되겠지.

그니까 [3초~4초) 에는 4명이 동시 시청중이었다는 거겠지? 

 

3. total_time[i] = total_time[i] + total_time[i - 1]

이걸 한 번 더 해주면 0초부터 매초까지의 누적 시청 초를 구할 수 있다.

[1,2,3,4,3,2,1,0]를 예로 들면

[1,3,6,10,13,15,16,16]

그니까 0초~5초까지 모든 시청자들의 누적 시청시간을 합치면 13초라는거다.

그럼 x초~y초까지의 누적 시청 시간은 차를 이용해서 구할 수 있다. total_time[y]-total_time[x]이런식으로 하면 되겠지?

 

4. 근데 마지막 과정이 이해가 안된다. ㅋㅋㅋ 해설을 그대로 복붙해보겠다.

마지막으로 정답을 구하는 과정입니다.

for i = (adv_time_sec - 1) ~ (play_time_sec - 1)
    if ( i >= at) 
        max_time = max(max_time, total_time[i] - total_time[i - at] )
    else 
        max_time = max(max_time, total_time[i])

위 코드는 반복문을 돌며 시각 i - at + 1에 광고를 넣을 때의 누적 재생 시간을 구하여, 그중에서 가장 긴 시간을 max_time에 넣어주고 있습니다. max_time 값이 마지막으로 업데이트될 때의 시각 i - at + 1을 HH:MM:SS 형태로 변환한 값이 문제에서 요구하는 정답입니다.

 

i가 광고길이만큼의 시점부터 끝까지 iteration이 도는건 이해하겠는데

그 내부에 at이 뭔질 모르겠네. 아..? adv_time 그러니까 광고의 길이인가? 그럼

total_time[i - at]가 이해가 된다.

if i>=at 그러니까 i를 광고의 마지막 지점으로 삽입할 수 있을만큼의 여유공간이 앞에 있으면

i-at+1에 광고를 넣는다고 가정하고 누적시간을 구해서 갱신하는거지.

i < at라면 0초부터 i초까지의 total 누적시간과 max_time을 그냥 비교해서 갱신하고.

근데 i<at인 경우가.. 제일 첫 iteration밖에 없지 않나? adv_time_sec - 1부터 시작하니까..

굳이 이걸 반복문 내에 제어문으로 넣었어야 했나 싶네.

 

def to_sec(timestr):
    h,m,s = tuple(map(int,timestr.split(':')))
    return h*3600+m*60+s

def to_str(timesec):
    h = timesec // 3600
    timesec %= 3600
    m = timesec // 60
    timesec %= 60
    s = timesec
    return f'{h:02d}:{m:02d}:{s:02d}'

def solution(play_time, adv_time, logs):
    playtime = to_sec(play_time)
    advtime = to_sec(adv_time)
    
    if advtime >= playtime:
        return "00:00:00"
    
    log_start = []
    log_end = []
    for log in logs:
        log = log.split('-')
        log_start.append(to_sec(log[0]))
        log_end.append(to_sec(log[1]))
    
    totaltime = [0] * (playtime+1)

    for i in range(len(logs)):
        totaltime[log_start[i]] += 1
        totaltime[log_end[i]] -= 1
    
    for i in range(1,playtime+1):
        totaltime[i] += totaltime[i-1]
        
    for i in range(1,playtime+1):
        totaltime[i] += totaltime[i-1]
        
    maxtime = totaltime[advtime-1]
    answer = 0
    for i in range(advtime,playtime):
        if totaltime[i]-totaltime[i-advtime] > maxtime:
            maxtime = totaltime[i]-totaltime[i-advtime]
            answer = i-advtime+1

    
    return to_str(answer)