[Programmers] 광고 삽입(Level 3) / Python

https://programmers.co.kr/learn/courses/30/lessons/72414

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

 

풀이 과정 아이디어

1. H:M:S을 초단위로 변경
2. DP 사용(초 단위의 list를 저장)
3. log의 시작 시간과 끝나는 시간을 +1 / -1을 대입
   • 끝나는 시간에는 시청자가 빠져나가기 때문에 -1을 대입
   • 이후 이전의 정보를 저장해줌으로써 해당 시간에 시청자 수 확인 가능
4. 해당 시간 별 누적 시청자를 계산하기 위해 위의 과정 반복
5. 광고 시간부터 플레이 타임 까지 계산(광고 시간만큼만 계산되는 경우도 고려)

def second_to_time(second) :
    h = str(second // 3600)
    if len(h) == 1 :
        h = '0' + h
    second = second % 3600
    m = str(second // 60)
    if len(m) == 1 :
        m = '0' + m
    second = second % 60
    s = str(second)
    if len(s) == 1 :
        s = '0' + s
    return h + ':' + m + ':' + s

def time_to_second(time) :
    h, m, s = map(int, time.split(':'))
    return 3600 * h + 60 * m + s

def solution(play_time, adv_time, logs):
    play_time = time_to_second(play_time)
    adv_time = time_to_second(adv_time)
    dp = [0] * (play_time + 1)
    dp_accumulate = [0] * (play_time + 1)
    for i in logs :
        start, end = i.split('-')
        start = time_to_second(start)
        end = time_to_second(end)
        dp[start] += 1
        dp[end] -= 1

    for j in range(1, play_time + 1) :
        dp[j] = dp[j] + dp[j-1]
        dp_accumulate[j] = dp[j] + dp_accumulate[j-1]

    max_time = 0
    most_view = 0

    for l in range(adv_time - 1, play_time + 1) :
        if l < adv_time :
            most_view = dp_accumulate[l]
            max_time = l - adv_time + 1
        else :
            if most_view < dp_accumulate[l] - dp_accumulate[l - adv_time] :
                most_view = dp_accumulate[l] - dp_accumulate[l - adv_time]
                max_time = l - adv_time + 1

    return second_to_time(max_time)