[Kakao] 광고 삽입 Python3

문제보러가기

- https://tech.kakao.com/2021/01/25/2021-kakao-recruitment-round-1/

풀이

• 기출을 통해 느낀바로는 카카오는 시간 혹은 기간을 사용한 문제를 좋아하는 것 같습니다.
• 이 문제 또한 주어진 String 값을 시간(초)으로 변환하고, 주어진 포맷으로 반환하여야 합니다.
• 따라서 strTosec, secTostr 함수를 구현하여 주어진 값을 활용할 수 있도록 했습니다.
• 또한, 주어진 범위가 00:00:01 이상 99:59:59 임으로 100시간 즉 360,000초 입니다.
• 즉, 영상 시간의 초 단위 사이즈로 배열을 잡는데 무리가 없음을 알 수 있습니다.
  • view = [0 for _ in range(play_sec+1)]
• logs를 순회하며 i초에 시청하는 사람수를 업데이트 하고 구간합을 구하는 방법을 우선적으로 떠올리게 됩니다.
• 하지만 그렇게 구현을 하게되면 logs를 순회하며 업데이트를 할때O(len(logs)시청시간) = 300,000*360,000 => 약 1000억으로 시간복잡도를 통과하지 못하게 된다.
• 따라서, 구간의 시작(+1), 구간의 끝(-1)을 len(logs) 만큼 표시하고 view[i] = view[i] +view[i-1]으로 한번에 구간별 시청자 수를 업데이트 하게되면 O(len(logs) + 영상시간) = 300,000 +360,000 으로 개선할 수 있다.
• 여기서 수학적 인사이트가 필요합니다.
• 최종적으로 광고를 가장 많이 시청한 구간을 찾기위해서 우리는 i 시간에서 i+adv_sec 사이의 시청자수가 가장 많은 구간을 찾아야 합니다.
• 이를 위해서, 위의 식을 다시 한번 사용하여 모든 구간의 시청자를 누적합니다.
• 그리고, view[i] - view[i-adv_sec] (구간 누적 시청자) 가 가장 많은 시간을 탐색합니다.

코드

def strTosec(s):
    return int(s[:2])*3600 + int(s[3:5])*60 + int(s[6:]) 

def secTostr(n):
    return f'{str(n//3600).zfill(2)}:{str((n%3600)//60).zfill(2)}:{str((n%3600)%60).zfill(2)}'

def solution(play_time, adv_time, logs):

    play_sec = strTosec(play_time)
    adv_sec = strTosec(adv_time)

    view = [0 for _ in range(play_sec+1)]

    for log in logs:
        start_sec = strTosec(log[:8])
        end_sec = strTosec(log[9:])
        view[start_sec] +=1
        view[end_sec] -=1

    for i in range(1, len(view)):
        view[i] += view[i-1]

    for i in range(1, len(view)):
        view[i] += view[i-1]

    max_view = view[adv_sec-1]
    answer = 0

    for i in range(adv_sec, play_sec):
        tmp = view[i]-view[i-adv_sec]
        if max_view < tmp:
            max_view = tmp
            answer = i-adv_sec+1

    return secTostr(answer)