"""
출처:프로그래머스
https://school.programmers.co.kr/learn/courses/30/lessons/72414

"""
# 풀이 과정
"""
주어진 변수:
play_time: 재생시간, adv_time:재생시간 길이 logs:시청자들이 시청한 구간정보

목표: 누적 재생시간이 나오는 곳에 공익광고 삽입

시작시간 구하기(여러 개라면 제일 빠른 시간)

생각방향: 주어진 광고시간을 초당으로 누적인원을 집계했을 때 가장 많이 본 시간의 시작점 구하기

모두 초로 바꿔서 구하기 
"""


def solution(play_time, adv_time, logs):
    play = play_time.split(":")
    play = list(map(int, play))

    # 플레이타임을 모두 초로 변경
    p = play[0] * 60 * 60 + play[1] * 60 + play[2]

    # 초당 뷰 체크 목록
    view_check = [0] * (p + 1)

    adver = adv_time.split(":")
    adver = list(map(int, adver))

    # 광고 시간을 모두 초로 변경
    adver = adver[0] * 60 * 60 + adver[1] * 60 + adver[2]

    l = []

    for i in logs:
        # - 제거
        viewer = i.split("-")
        v_start = viewer[0]
        v_end = viewer[1]

        # : 제거
        v_start = v_start.split(":")
        v_start = list(map(int, v_start))

        v_end = v_end.split(":")
        v_end = list(map(int, v_end))

        v_start = v_start[0] * 60 * 60 + v_start[1] * 60 + v_start[2]
        v_end = v_end[0] * 60 * 60 + v_end[1] * 60 + v_end[2]

        l.append((v_start, v_end))

    # 각 초별 시청자 집계
    for start, end in l:
        view_check[start] += 1
        view_check[end] -= 1

    # 시간별 집계
    for i in range(len(view_check)):
        view_check[i] += view_check[i - 1]

    # 합 집계
    prefix_sum = [0] * len(view_check)

    prefix_sum[0] = view_check[0]

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

    # 최고점 기록
    best_view = prefix_sum[adver - 1]
    best_time = 0

    for i in range(adver, len(view_check)):
        if prefix_sum[i] - prefix_sum[i - adver] > best_view:
            best_view = prefix_sum[i] - prefix_sum[i - adver]
            best_time = (i - adver + 1)

    result = ""

    # best_time 변환
    hour = best_time // 3600

    if len(str(hour)) == 1:
        h = str(0) + str(hour)

    else:
        h = str(hour)
    result = result + h + ":"

    minute = (best_time - 3600 * hour) // 60

    if len(str(minute)) == 1:
        m = str(0) + str(minute)
    else:
        m = str(minute)
    result = result + m + ":"

    second = best_time - 3600 * hour - 60 * minute

    if len(str(second)) == 1:
        s = str(0) + str(second)
    else:
        s = str(second)

    result = result + s

    return result