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

1. 문제

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

 

2. 코드

python 1

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

def seconds_to_time(time):
    h, rem = divmod(time, 3600)
    m, s = divmod(rem, 60)
    
    return f"{h:02d}:{m:02d}:{s:02d}"

def solution(play_time, adv_time, logs):
    answer = 0
    
    # 시분 -> 초로 변경
    play_time_seconds = time_to_seconds(play_time)
    adv_time_seconds = time_to_seconds(adv_time)
    
    # 누적합 배열 생성
    total_time = [0] * (play_time_seconds + 1)
    
    for log in logs:
        start_time, end_time = log.split("-")
        start_time_seconds = time_to_seconds(start_time)
        end_time_seconds = time_to_seconds(end_time)
        total_time[start_time_seconds] += 1
        total_time[end_time_seconds] -= 1
    
    # 각 시점의 동시 시청자 수 
    for i in range(1, play_time_seconds + 1):
        total_time[i] += total_time[i-1]

    # 시청자 수의 누적합
    for i in range(1, play_time_seconds + 1):
        total_time[i] += total_time[i-1]
    
    max_value = total_time[adv_time_seconds - 1]
    
    # 시청자의 누적합에서 최적의 광고 시간 확인
    for start in range(play_time_seconds - adv_time_seconds + 1):
        end = start + adv_time_seconds - 1
        current = total_time[end] - total_time[start - 1]        
        
        if current > max_value:
            max_value = current 
            answer = start 
            
    return seconds_to_time(answer)

풀이

1. 모든 시간을 초로 변경 함
2. 재생 시간만큼 [0] 생성
3. logs에 대해
   1. 시작시간에 +1 기록
   2. 종료 시간에 -1 기록
4. 첫번째 누적합을 통해 각 초의 동시 시청자 수를 구함
5. 두번째 누적합을 통해 0 초부터 해당 초까지의 누적 시청 시각 구함
6. 시청자의 누적합에서 최적의 광고 시간 시작 점 찾기
   1. end = 시작시간 + 광고길이 - 1시작이 0초일 때 → 광고 구간: 0, 1, 2
   2. 시작이 5초일 때 → 광고 구간: 5, 6, 7
   3. ex) 광고 길이 = 3초일때
   4. current = 0~end의합 - 0~start - 1의합start = 1, end = 2라면 → 광고 구간 = 1~2초⇒ But 시청자의 누적 합[2] - 시청자의 누적 합[1] = 6 - 3 = 3

따라서 start~end의 누적 시청시간 = 0~end의 누적 합 - 0~start - 1의 누적 합

1. 1. 원하는 값 = 1, 2
   2. ex) 시청자 = [1,2,3,4], 시청자의 누적 합 = [1,3,6,10]
   3. max_value - 첫 광고 구간의 누적 시청 시간 값

 

python 2

def solution(play, adv, logs):
    c = lambda t: int(t[0:2]) * 3600 + int(t[3:5]) * 60 + int(t[6:8])
    play, adv = c(play), c(adv)
    logs = sorted([s for t in logs for s in [(c(t[:8]), 1), (c(t[9:]), 0)]])

    v, p, b = 0, 0, [0] * play
    for t, m in logs:
        if v > 0:
            b[p:t] = [v] * (t - p)
        v, p = v + (1 if m else -1), t

    mv, mi = (s := sum(b[:adv]), 0)
    for i, j in zip(range(play - adv), range(adv, play)):
        s += b[j] - b[i]
        if s > mv:
            mv, mi = s, i + 1

    return f"{mi//3600:02d}:{mi%3600//60:02d}:{mi%60:02d}"

 

3. 메모

• python 1
  • 내 풀이
  • 누적합 사용
  • 시간 복잡도 : O(N + L)
• python 2
  • 다른 사람 풀이
  • 슬라이딩 윈도우
  • 시간 복잡도: O(LlogL + N)
• 구간을 여러 번 더하거나, 겹치는 범위 계산 → 누적 합, IMOS 사용 우선