[Python] 광고 삽입

1. 문제

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

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

2. 풀이

• 예전에 풀었던 문제에서 나왔던 누적합 개념을 써먹어서 너무 기쁨!!!!취준 코테에도 나오면 좋겠다^^*
• 누적합을 써도 시간 초과가 나와서
  • adv(광고 길이) 단위로 계속 합치는 것이기 때문에 dp로 더해주었더니 풀림
  • 누적합으로 시간복잡도가 n^2 -> n*4 로 바뀜
• 중간에 몇개가 틀리는데 이유를 모르겠어서 검색해봤더니 끝나는 시간 미만으로 생각해야 한다해서 +1 붙였던 것들을 뺐더니 맞았음

3. 코드

def stringtotime(str_time):
    h,m,s = str_time.split(":")
    h,m,s = int(h),int(m),int(s)
    return h*3600 + m*60 + s
    
def timetostring(int_answer):
    answer = ''
    if (int_answer // 3600) >= 10:
        answer += str(int_answer // 3600)
    else:
        answer += "0" + str(int_answer // 3600)
    answer += ":"
    if ((int_answer % 3600 )//60) >= 10:
        answer += str((int_answer % 3600 )//60)
    else:
        answer += "0" + str((int_answer % 3600 )//60)
    answer += ":"
    if ((int_answer % 3600)%60) >= 10:
        answer += str((int_answer % 3600)%60)
    else:
        answer += "0" + str((int_answer % 3600)%60)
    return answer
    
def solution(play_time, adv_time, logs):
    answer = ''
    time_dict = []
    end = stringtotime(play_time)
    adv = stringtotime(adv_time)

    time_dict = [0]*(end + 2)
    
    for i in logs:
        stt, fin = i.split("-")
        stt = stringtotime(stt)
        fin = stringtotime(fin)
        time_dict[stt] += 1
        time_dict[fin] -= 1

    for i in range(1,end+1):
        time_dict[i] = time_dict[i] + time_dict[i-1]
        
    # 누적합
    int_answer = 0
    list_sum = []
    elem = 0
    
    # 0-adv시간까지 본사람 숫자 세기
    for i in range(adv):
        elem += time_dict[i]
    list_sum.append(elem)
    max_time = elem
    
    # 
    for i in range(1,end - adv+1):
        elem = list_sum[i-1] - time_dict[i-1]+ time_dict[adv+i-1]
        list_sum.append(elem) 
        if elem > max_time :
            max_time = elem
            int_answer = i
            
    answer = timetostring(int_answer)
    # print(answer)
    return answer