[Python] 프로그래머스 level3 광고 삽입

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

풀이 과정 

• 처음에는 후보가 될 수 있는 시작지점을 구해서 각 log와 비교해줬더니 O(N^2)로 시간초과가 났다. 
• 모든 시점에 각각 시청하는 사람이 몇명인지 배열에 저장하면, O(전체시간)으로 비교 가능하다. 
• 각 시간마다 사람 수를 저장하는 방법이 O(전체시간 * 전체사람)으로 밖에 안떠올랐는데, dp memorize를 사용하면 O(전체시간)으로 저장할 수 있다. 

• "HH:MM:SS"문자열을 초로 변환해주는 함수와 초를 "HH:MM:SS"형태로 변환해주는 함수를 만든다. 
• 위 그럼처럼 각 시점에 맞는 사람수를 구하기 위해 dp[i]를 갱신해주고, 구간합 계산을 위해 dp[i]를 한 번 더 갱신해 준다. 

# 광고 삽입

def strtoint(time):
    answer = int(time[0:2])*60*60
    answer += int(time[3:5])*60
    answer += int(time[6:])
    return answer
def inttostr(time):
    hour = time//3600
    minute = (time%3600)//60
    second = (time-hour*3600-minute*60)
    answer = str(hour).zfill(2) + ':'
    answer += str(minute).zfill(2) + ':'
    answer += str(second).zfill(2)
    return answer

def solution(play_time, adv_time, logs):
    play_time = strtoint(play_time)
    adv_time = strtoint(adv_time)
    dp = [0]*(play_time+1)
    for x in logs:
        start = strtoint(x[:8])
        end = strtoint(x[9:])
        dp[start] += 1
        dp[end] -= 1
    for i in range(1, play_time+1):
        dp[i] = dp[i]+dp[i-1]
    for i in range(1, play_time+1):
        dp[i] = dp[i]+dp[i-1]
    answer = 0
    max_cnt = dp[adv_time]
    for start in range(1, play_time):
        if start+adv_time >= play_time:
            end = play_time
        else:
            end = start+adv_time
        if max_cnt < dp[end]-dp[start]:
            max_cnt = dp[end]-dp[start]
            answer = start+1
    return inttostr(answer)