[Programmers] 광고 삽입 문제 풀이 (Python)

1. 문제 풀이

추석 트래픽에 이어서 시간을 활용한 문제이다. 시간과 같이 구간을 활용하는 문제는 주의할 점이 있는데 바로 마지막 지점이 포함이 되는지∙되지 않는지 체크해야한다. 이번 문제는 마지막 지점을 포함하지 않는 문제이다.

다음의 과정을 거쳐 문제를 풀었다.

1. 입력으로 들어오는 시간 hh:mm:ss → 초 단위로 변경
   • 01:00:01 ⇒ 3601
2. 각 시간 때마다 들어오는 사람, 나가는 사람을 record 배열에 초기화 한다.
   • $\text{record[i]}$: i번째 시간에 들어오는 사람의 수
     • 각 log마다 시작 시간에는 시청하는 사람이 추가되므로 record[i] += 1
     • 종료 시간에는 시청하는 사람이 빠지므로 record[i] -= 1
     • 이런 방식으로 record 배열을 초기화시킨다
3. $\text{record[i]}$을 누적합한다.
   • 1번째 누적합: ‘i번째 시간(초)에서 시청하는 사람의 수’
   • 2번째 누적합: 부분합을 구하기 위한 누적합
     • t시간에서 t+i 시간까지 누적 재생시간을 구할려면 1번째 누적합만 사용시 $\text{sum(record[t:t+i])}$을 해주어야한다. 하지만 $\text{sum}$함수는 $\text{O(n)}$이므로 현재 문제에서는 사용할 수가 없다
     • 따라서 한 번 더 누적합을 시켜 구간별 누적 재생시간을 구한다.
4. 구간별 누적 재생시간을 구한다.
   • 누적 재생시간의 끝 지점이 i이고 광고 시간이 adv_t일 때 누적 재생시간: $\text{record[i-1] - record[i- adv_t -1]}$
     • 시작 지점은 포함하고 마지막 지점은 포함하지 않기 때문에 식이 이렇게 나온다.
5. 누적 재생시간이 가장 높은 시작지점을 형식에 맞춰 반환한다.

Tip

• 합을 구해야한다면 부분합을 이용하는 것도 생각해보자!
• 시간을 가장 작은 단위(second, ms)로 변형하면 다양한 자료형을 통해 더 나은 technique을 사용할 수 있다.

2. 코드

def str2time(time_string):
    h,m,s = time_string.split(":")
    return int(h) * 3600 + int(m) * 60 + int(s)

def time2str(time_number):
    h,m,s = (time_number // 3600), (time_number % 3600 // 60), (time_number % 3600 % 60)
    h = str(h) if len(str(h)) == 2 else '0' + str(h)
    m = str(m) if len(str(m)) == 2 else '0' + str(m)
    s = str(s) if len(str(s)) == 2 else '0' + str(s)
    return ":".join([h, m, s])

def solution(play_time, adv_time, logs):
    play_t, adv_t = str2time(play_time), str2time(adv_time)

    if play_t == adv_t: return '00:00:00'

    record = [0] * (play_t+1)
    for log in logs:
        start_time, end_time = log.split("-")
        start_t, end_t = str2time(start_time), str2time(end_time)
        record[start_t] += 1
        record[end_t] -= 1

    for _ in range(2):
        for i in range(1, play_t+1):
            record[i] += record[i-1]

    start_t, max_t = 0,record[adv_t-1]
    for i in range(adv_t+1,play_t+1):
        temp = record[i-1] - record[i-adv_t-1]
        if temp > max_t:
            start_t,max_t = i-adv_t, temp

    return time2str(start_t)