광고 삽입

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

코딩테스트 연습 - 광고 삽입

def solution(play_time, adv_time, logs):
    
    def time_to_sec(time): # HH:MM:SS to seconds
        time = list(map(int, time.split(':')))
        return time[0] * 3600 + time[1] * 60 + time[2]
    def sec_to_time(time): # seconds to HH:MM:SS 
        result, x = [], 3600
        for i in range(3):
            result.append(str(int(time//x)).zfill(2))
            time %= x
            x /= 60
        return ':'.join(result)
    
    answer = 0
    play_time = time_to_sec(play_time) # 영상 재생시간
    adv_time = time_to_sec(adv_time) # 광고 길이
    
    vewers = [0 for i in range(play_time + 1)] # 영상의 초당 시청자
    for l in logs:
        s, e = l.split('-')
        start = time_to_sec(s)
        end = time_to_sec(e)
        vewers[start] += 1 # start(초)에 시청자 1명 증가
        vewers[end] -= 1 # end(초)에 시청자 1명 감소

    for i in range(1, len(vewers)): # 초당 시청자 현황 ex. vewers[x] : x초때 시청자 수
        vewers[i] += vewers[i - 1]

    for i in range(1, len(vewers)): # 해당 초까지의 누석 시청자
        vewers[i] += vewers[i - 1]

    max_ = vewers[adv_time - 1] - 0 # 0초부터 광고를 했을때 시청자 수
    for i in range(0, len(vewers) - adv_time):
        if vewers[i + adv_time] - vewers[i] > max_: # 현재 구간 시청자 수가 max 갱신
            max_ = vewers[i + adv_time] - vewers[i]
            answer = i + 1

    return sec_to_time(answer)

→ 이때까지 푼 문제들 중에서 가장 많은 시간을 써보았지만 결국 카카오 해설에서 힌트를 보고 풀었다.

처음 접근은 추석 트래픽문제 처럼 했는데, 지금 생각해보면 당연한 결과지만 logs가 너무 많아서 시간 초과에 걸렸다.

 

play_time을 초당 배열로 만들고, 

for문을 두 번 반복하면서 (초당 시청자수로 초기화) → (초당 누적 시청자수로 갱신) 을 해준 다음,

 A ~ B 사이의 시청자수 = B초에서의 누적 시청자수 - A초에서의 누적 시청자수

를 이용해서 답을 도출해주는데... 

처음 접하는 풀이법이라 힌트를 안보고 시간을 더 가졌어도 쉽게 떠오르지 않았을 것 같다.

 

하지만 문제의 제한 사항을 주의 깊게 보면 다음 부터는 효율적으로 풀이 방법을 찾아낼 수 있겠다.

실패한 풀이) logs는 최대 300,000개이다. 

→ 추석 트래픽 방법을 사용하면 검사해야 하는 checkpoint는 600,000개 이고,

각 checkpoint에서 logs를 또 다시 순차 검색하며 각각 시청 시간을 계산해야한다. O(N^2)

적어도 이런 방법을 의도한 문제는 아닐것임.

이정도는 생각하고 문제를 풀자.