[PG/Python] 광고 삽입

📌 문제

https://programmers.co.kr/learn/courses/30/lessons/72414?language=python3 

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

 

📌 문제 접근 방법

1. 아이디어를 참고한 풀이 : https://dev-note-97.tistory.com/156
2. 시간을 모두 초로 바꾸어서 Memoization을 사용한다.
3. 로그의 시간을 all_time 리스트에 저장할 때, 반복문을 사용해서 start부터 end-1까지 1을 더해줬는데, 이 경우엔 시간초과가 발생했다. -> start에 +1, end에 -1을 한 뒤 리스트의 값들을 계속 더해주면 반복문을 한 번만 써서 해결할 수 있다.
4. 광고 구간에서 재생 중인 시청자의 수를 구하기 위해서 '광고 시작 시간 ~ 광고 끝 시간'에서 시청자 수를 모두 더해야 하는데 이 경우에도 시간초과가 우려된다. -> 위와 같은 방법으로 반복문 하나로 누적합을 만들면 광고 구간의 시청자 수를 구하기 훨씬 간편하다.
5. 누적합 리스트를 활용해서 정답을 구하고 원하는 출력 형식으로 변환해서 반환한다.

 

📌 코드

# 프로그래머스 광고삽입

def solution(play_time, adv_time, logs):

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


    def time_format(time):
        if time < 10:
            return '0'+str(time)
        
        return str(time)


    play_time = str_to_sec(play_time)
    adv_time = str_to_sec(adv_time)

    all_time = [0 for _ in range(play_time+1)]
    for log in logs:
        start, end = log.split('-')

        start = str_to_sec(start)
        end = str_to_sec(end)

        all_time[start] += 1
        all_time[end] -= 1
    
    for i in range(1, play_time+1):
        all_time[i] += all_time[i-1]
    
    # 구간합을 구하기 위해 누적 값으로 바꾸기
    # [0, 1, 2, 2, 1] 에서 1~4초 구간합은 1(1~2초)+2(2~3초)+2(3~4초) = 5인데 
    # 누적 값으로 바꾸면 일일이 더하지 않고 인덱싱의 차로 구할 수 있음
    # [0, 1, 3, 5, 6] 에서 1~4초 구간합은 리스트[3](0~3초) - 리스트[0](0~1초) = 5
    for i in range(1, play_time+1):
        all_time[i] += all_time[i-1]
    
    max_cnt = 0
    max_time = 0
    for t in range(play_time-adv_time+1):
        if t:
            cnt = all_time[t+adv_time-1] - all_time[t-1]
        else:
            cnt = all_time[t+adv_time-1]
        
        if max_cnt < cnt:
            max_cnt = cnt
            max_time = t

    h, max_time = divmod(max_time, 3600)
    m, s = divmod(max_time, 60)

    return time_format(h) + ':' + time_format(m) + ':' + time_format(s)