[카카오 기출] 광고 삽입

https://programmers.co.kr/learn/courses/30/lessons/72414?language=python3 

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

 

def toNum(str1):
    hh, mm, ss = map(int, str1.split(':'))
    return hh*3600 + mm*60 + ss

def toTime(num):
    str1 = ''

    hh = num//3600
    if hh < 10:
        str1 += '0'+str(hh)
    else:
        str1 += str(hh)
    str1 += ':'

    num = num % 3600
    mm = num//60
    if mm < 10:
        str1 += '0'+str(mm)
    else:
        str1 += str(mm)
    str1 += ':'

    ss = num%60
    if ss < 10:
        str1 += '0'+str(ss)
    else:
        str1 += str(ss)

    return str1

import collections
import heapq
def solution(play_time, adv_time, logs):
    play_time = toNum(play_time)
    adv_time = toNum(adv_time)
    
    info = []
    for i in range(len(logs)):
        start, end = logs[i].split('-')
        start, end = toNum(start), toNum(end)
        info.append([start, end])
    info.sort(key = lambda x: (-x[0], -x[1]))
    
    q = []
    sum_num = 0
    sum_time = [0] * (play_time)

    for i in range(info[-1][0], play_time):
        while info and i == info[-1][0]:
            _, end = info.pop()
            heapq.heappush(q, end)
            sum_num += 1

        while q:
            elem = heapq.heappop(q)
            if elem == i:
                sum_num -= 1
            else:
                heapq.heappush(q, elem)
                break

        sum_time[i] = sum_num
    
    init_time = 0
    cur = sum(sum_time[:adv_time])
    max_val = cur
    for i in range(1, play_time-adv_time+1):
        cur = cur - sum_time[i-1] + sum_time[i+adv_time-1]
        if max_val < cur:           
            max_val = cur
            init_time = i

    return toTime(init_time)

최적화에 신경을 써야 시간 안에 풀 수 있다.

 

첫번째로 버벅거렸던 부분은 log 정보를 읽어와 배열에 더해주는 것인데

단순히 log 하나씩을 읽어와서 일일이 해당 배열 위치에 +1을 해주는 방식으로는 시간 초과가 날 것 같아서

log를 정렬하여 시작시간이 작은 순서대로 하나 씩 뽑아내면서 현재의 sum_num 값을 조절해주면서 해당 배열에 넣어주는 방식으로 했다. 이때 heapq를 적절히 사용하면서 끝나는 시간이 되면 q에 있던 원소를 빼주어야 한다. 그러면서 sum_num 값을 조절해준다.

오랜 시간 문제가 풀리지 않았던 이유가 시작시간이 동일한 로그가 여러 개일 때를 간과했다. 49번째 줄에 while을 써야할 자리에 if를 써서 문제가 계속 풀리지 않았다.

 

최적화를 위해 마지막에 반복문을 돌면서 max_val을 업데이트 해주는 부분에서 

cur를 효율적으로 계산하기 위해 이전 배열값을 빼고 다음 배열값을 추가해주는 방식을 사용했다.