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

문제

• 전체 영상의 길이와 시청자들의 재생 구간이 주어질 때, 공익 광고의 최적의 삽입 구간 찾기
  • 시청자들의 누적 재생시간이 가장 큰 구간 찾아야 한다. 동일하다면 더 빠른 시각을 리턴한다.
  • 00:00:01 <= HH:MM:SS <= 99:59:59
  • 1 <= 시청자들 재생 구간 개수 <= 300,000

 

풀이

• 전체 재생 시간을 초당 나눠서 누적 시청자 수를 센다.
• 광고 시간 범위 내에서 누적 시청자 수의 최댓값을 찾는다. (단순 반복)
• 시작 시간을 다시 문자열로 변경해 리턴한다.

 

# HH:MM:SS 를 초로 나타내기
def time_split(time):
    h, m, s = map(int, time.split(":"))
    return h*3600 + m*60 + s

def solution(play_time, adv_time, logs):
    play_time = time_split(play_time)   
    adv_time = time_split(adv_time)
    times = [0 for _ in range(play_time+1) ]

    for log in logs:
        start, end = map(time_split, log.split("-"))
        
        times[start] += 1
        if end == play_time :
            continue
        times[end] -= 1

    for i in range(1, len(times)):      # 초당 시청자 수
        times[i] += times[i-1]
    
    for i in range(1, len(times)) :     # 초당 누적 시청자 수
        times[i] += times[i-1]
        
    cur = times[adv_time - 1]        	# 0 ~ adv_time 시청자 수
    start_time = 0
    for t in range(adv_time, play_time):# 광고 시작 시각 찾기 (start_time)
        if cur < times[t] - times[t-adv_time] :
            cur = times[t] - times[t-adv_time]
            start_time = t - adv_time + 1
	
    # HH:MM:SS 형태로 변환
    h = str(start_time // 3600).zfill(2)
    start_time = start_time % 3600
    m = str(start_time // 60).zfill(2)
    start_time = start_time % 60
    s = str(start_time).zfill(2)

    return h + ":" + m + ":" + s

 

References

• 프로그래머스 Lv3 광고 삽입