[프로그래머스] 광고 삽입

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

프로그래머스

🤔 문제분석

알아야할 개념

• 누적합

스트링 타입의 시간을 초 단위로 컨버팅 해주는 함수와, 시간을 스트링 시간으로 컨버팅 해주는 함수를 만들었다.

1. 로그를 순회하면서 r_c 배열에 시작시간을 +1 끝나는시간을 -1을 해준다.
2. 이제 누적합을 이용해야하는데 p_s 배열에 r_c의 누적값을 저장한다.
   1. p_s[end_time-1] - p_s[start_time] 값에 겹치는 로그의 총 개수를 리턴하게 된다.
3. i는 0부터 play_time - adv_time을 두고, (i~adv_time) ~ (i ~ i + adv_time)를 순회하면서 가장 큰 값을 찾아낸다.

💻 코드

def solution(play_time, adv_time, logs):

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

    def sec_to_time(sec : int):
        return f'{sec//3600:02d}:{sec%3600//60:02d}:{sec%60:02d}'

    play_time = time_to_sec(play_time)
    adv_time = time_to_sec(adv_time)
    p_s = [0] * (play_time + 1)
    r_c = [0] * (play_time + 1)

    for log in logs:
        s, e = log.split("-")
        s = time_to_sec(s)
        e = time_to_sec(e)
        r_c[s] += 1
        r_c[e] -= 1

    for i in range(1, play_time + 1):
        r_c[i] += r_c[i-1]
        p_s[i] = p_s[i-1] + r_c[i]

    answer = max((p_s[start_time + adv_time - 1] - (p_s[start_time-1] if start_time - 1 > 0 else 0), -start_time) 
                 for start_time in range(play_time - adv_time +1))

    return sec_to_time(-answer[1])