[누적합] 광고 삽입 (python) - 카카오

문제

풀이

💡 1. 시간을 전부 초로 바꿔서 배열로 풀이하기

💡 2. 누적합

최종 코드

 

문제

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

프로그래머스

풀이

💡Idea!
1. 시간을 전부 초로 바꿔서 배열로 풀이하기
2. 누적합

💡 1. 시간을 전부 초로 바꿔서 배열로 풀이하기

• 시간, 분을 전부 초로 바꾸어

• 매초마다의 시청자수를 기록하는 배열을 만든다.

• 이를 통해 구간별 누적합을 구할 예정!

 

💡 2. 누적합

• adv_time 구간 동안의 합의 최대를 구하기 위해서

• 각 구간의 누적합(0~해당 시각까지의 모든 시청자수의 합)을 1차원 배열로 미리 구해 놓는다.
• 최종적으로 adv_time 구간 동안의 합은, 누적합들의 차를 이용해 구한다.

위 설명글보다는 코드랑 그림이 이해가 빠른 것 같다..!

1. 시작 시각/종료 시각 표시

times[start] += 1 
times[end] -= 1

1. 각 시각 마다의 시청자수 기록

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

1. 각 시각별 누적합 구하기 (0부터 해당 시각까지의 모든 누적합)

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

 

 

이렇게 누적합 1차원 배열을 만들어주면, 이를 통해 구간별 합의 최대를 구하면 된다.

    for i in range(adv_time-1, play_time):         
    	tmp = times[i] - times[i-adv_time] // 구간별 합         
    	if tmp > max_value:             
    		max_value = tmp             
    		answer = i - adv_time + 1

 

최종 코드

# 초로 환산하기
def get_seconds(time):
    h, m, s = map(int, time.split(":"))
    return (h*60*60) + (m*60) + s

# 시간을 문자열로
def time_to_str(time):
    h = time // (60**2)
    h = '0' + str(h) if h < 10 else str(h)
    time %= 60**2

    m = time // (60)
    m = '0' + str(m) if m < 10 else str(m)

    time %= 60
    s = '0' + str(time) if time < 10 else str(time)
    
    return h + ':' + m + ':' + s

def solution(play_time, adv_time, logs):  
    play_time = get_seconds(play_time)
    adv_time = get_seconds(adv_time)
    times = [0] * (play_time + 1)
    
    # 1. 시작/종료시간 기록
    for log in logs:
        start, end = log.split('-')
        start = get_seconds(start)
        end = get_seconds(end)
        # 시작, 종료지점 표시
        times[start] += 1
        times[end] -= 1

    # 2. 구간별 시청 기록 (+1 부터 -1까지)
    for i in range(1, play_time):
        times[i] += times[i-1]
    
    # 3. 누적 시청 기록
    for i in range(1, play_time):
        times[i] += times[i-1]

    max_value = -1
    answer = 0
    
    # 4. DP 배열을 이용한 누적합 구하기 : times[i] - times[i - adv_time]
    # i : 끝점, answer : 시작점
    # 끝점 기준으로 반복문
    for i in range(adv_time-1, play_time):
        tmp = times[i] - times[i-adv_time] 
        if tmp > max_value:
            max_value = tmp
            answer = i - adv_time + 1

    return time_to_str(answer)

 

 

Uploaded by Notion2Tistory v1.1.0