프로그래머스 광고 삽입

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

카카오 2021년인데 시간 문자열 파싱은 어느정도 적응했는데, 로직짜는데 어려웠다.
너무 어렵게 생각한 것 같다. 일단 패착의 요인은 최대 가능시간이 100시간인데, 이걸 초단위로 sliding window를 할때, 시간 초과가 날 것인가를 생각해봤을때 360000초이기 때문에 충분히 가능한 시간복잡도였다.

문제의 핵심은 결국 특정 구간에 대한 시청자들을 나타냈을때 구간합이 최대가 되는 곳의 시작점을 리턴하는것 이었다.
이 과정에서 각 초에 대한 시청자들의 수를 구하기 위해서 다음과 같이 나타낼 수 있었다

• a[start] += 1
• a[end] -= 1
• for i in range(1,len(a)):
  a[i] = a[i] + a[i-1]

이런식으로 표현하게 되면 시청자가 시청을 종료한 구간까지의 구간동안 시청자 수를 더할 수 있다.

시청자 수를 표현하는 배열을 슬라이딩 윈도우를 통해서 계속해서 합을 구해나간다면 구간합을 계속 더해야 하므로 시간초과가 날 수 밖에 없다.

그렇기 때문에 투 포인터를 이용해 처음 구간합에서 left를 빼고, right를 더해서 그 값이 최대시청자수와 비교해서 크다면 스위칭을 해주는 방식으로 시간초과를 해결할 수 있다.

from collections import deque
def solution(play_time, adv_time, logs):
    play_time = str_to_int(play_time)
    adv_time = str_to_int(adv_time)
    a = [0]*(play_time+1)
    q = getviewers(a,logs)
    viewer = sum(q[0:adv_time])
    max_viewer = viewer
    start = 0
    queue = deque(q[0:adv_time])
    for i in range(adv_time,play_time):
        viewer -= queue.popleft()
        viewer += q[i]
        queue.append(q[i])
        if max_viewer < viewer:
            start = i - adv_time + 1
            max_viewer = viewer
    return int_to_str(start)
    
    
def str_to_int(time):
    h,m,s = time.split(':')
    return int(h)*3600 + int(m)*60 + int(s)
def int_to_str(time):
    h = time // 3600
    h = f'0{str(h)}' if h < 10 else str(h)
    time %= 3600
    m = time // 60
    m = f'0{str(m)}' if m < 10 else str(m)
    time %= 60
    s = time
    s = f'0{str(s)}' if s < 10 else str(s)
    return f"{h}:{m}:{s}"

def getviewers(a,logs):
    for log in logs:
        start,end = log.split('-')
        start = str_to_int(start)
        end = str_to_int(end)
        a[start] += 1
        a[end] -= 1
    for i in range(1,len(a)): ## 구간별 시청자 구하기
        a[i] = a[i] + a[i-1]
    return a