[Python] Programmers 광고 삽입

1. 문제 링크

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

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

---

2. 문제 요약

시청자들의 누적 재생시간이 가장 많은 곳 찾기 ⇒ 누적합으로 구하기

[입력값]

• play_time: 동영상 끝나는 시간
• adv_time: 공익광고 재생 시간
• logs: 시청자들 시청하는 구간

[리턴 값]

• 광고 삽입할 시작 시간 - HH:MM:SS (str)

---

3. 아이디어 정리

누적합으로 해당 구간에 몇 명이 시청하는지 구한다.

1. 초 단위 별로 시청 시작 시각에는 + 1시청 끝 시각 -1 저장한다.
2. 1에서 구한 배열을 누적합을 만들어 특정 초에 몇 명이 시청하는지 구하기
3. 2번에서 구한 누적합을 또 누적 합하여 초별 누적 시청자 수를 구한다.
4. 3번에서 구한 결과를 슬라이딩 윈도우를 통해 특정 기간에 몇 명이 시청하는지 찾아 최대 시청하는 시작 시간을 구한다.

---

4. 문제 풀이

4-1. 내 풀이

"""
 슬라이딩 윈도우
 부분합 - 시작과 종료를 담는 부분합
"""

def get_second(time):
    h, m, s = time.split(":")
    return int(h) * 3600 + int(m) * 60 + int(s)

def get_log_time(adv):
    s, e = adv.split("-")
    return (get_second(s), get_second(e))

def get_str_time(seconds):
    m, s = divmod(seconds, 60)
    h, m = divmod(m, 60)
    return '{:02d}:{:02d}:{:02d}'.format(h, m, s)

def solution(play_time, adv_time, logs):
    """
     시청자들의 누적 재생시간이 가장 많은 곳 찾기
    :param play_time: 광고 끝나는 시간
    :param adv_time: 공익광고 재생시간
    :param logs: 시청자들 시청하는 구간
    :return: 광고 삽입할 시작 시간 - HH:MM:SS
    """
    # 1. 모든 시간을 초로 변환
    play_time = get_second(play_time)
    adv_time = get_second(adv_time)

    # 2. 전체 초를 배열로 담기
    log_time = [0 for _ in range(play_time + 1)]
    for log in logs:
        start, end = get_log_time(log)
        log_time[start] += 1
        log_time[end] -= 1
    # 2. log_time 부분합 구하기 - 특정 초에 시청되는 인원 파악
    for i in range(1, len(log_time)):
        log_time[i] += log_time[i - 1]

    # 3. 두번째 부분합을 진행하여 누적 시청자 파악
    for i in range(1, len(log_time)):
        log_time[i] += log_time[i - 1]

    # 4. 슬라이딩 윈도우 - 누적합으로 가장 많이 시청하는 인원 찾기
    result_time = 0  # 가장 많이 시청한 시간
    result_cnt = 0   # 가장 많이 시청한 사람 수
    for end in range(adv_time - 1, play_time):
        if end >= adv_time:   # end가 광고 시간보다 커야 누적합 구하기 가능
            if result_cnt < log_time[end] - log_time[end - adv_time]:
                result_cnt = log_time[end] - log_time[end - adv_time]
                result_time = end - adv_time + 1
        else:  # 광고 끝나는 시간이 광고시간보다 작은 경우
            if result_cnt < log_time[end]:
                result_cnt = log_time[end]   # 0~end 시간 누적
                result_time = 0              # 광고 삽입 시작시간: 0초

    return get_str_time(result_time)

---

5. 결론

• 2번 누적합을 진행해서 슬라이딩 윈도우로 푸는 문제이다.
• 누접합&슬라이딩 윈도우 문제 중 내 기준 가장 어려운 문제 😢