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

출처: 프로그래머스 코딩 테스트 연습, [프로그래머스] 광고 삽입

풀이

처음엔 각 시청자들이 영상을 재생한 구간을 전체 영상에 +1이런 식으로 표시하고 누적합을 이용해서 구하려 했으나 시간초과가 났다. 다시 문제를 보니 각 시청자들이 영상을 재생한 구간이 300,000개 이고 크기도 전체 영상의 크기보다 작거나 같으므로 엄청나게 큰 수가 나와 시간초과가 나겠구나 생각했다. 그래서 +1 하는 부분을 어떻게 시간을 단축시킬까 하다가 이전에 부분합 문제를 푼 기억이 있어 바로 적용해보았다. 그때는 잘 이해가 가지 않았지만 이번에 필요에 의해 부분합을 사용하니까 바로 이해가 되었다.

1. 시간문자열을 숫자로 바꾸는 메서드와 숫자를 시간문자열로 바꾸는 메서드를 만든다.
2. 전체 시간을 리스트로 만들고 각 인덱스는 시간을 뜻한다.
3. 각 로그들의 시작시간은 +1 끝시간은 -1을 하여 부분합을 만들어 준다.
4. 만든 부분합으로 누적합을 만들어 준다.
5. 광고시간크기 만큼 움직이며 끝시간 - 시작시간을 하여 최대가 되는 구간을 구한다.

코드

def solution(play_time, adv_time, logs):
    
    def timeToInt(str):
        h, m, s = str.split(':')
        return int(h) * 60 * 60 + int(m) * 60 + int(s)
    
    def intToTime(num):
        h, other = num // 3600, num % 3600
        m, s = other // 60, other % 60
        return str(h).zfill(2) + ':' + str(m).zfill(2) + ':' + str(s).zfill(2)
    
    playTime, advTime = timeToInt(play_time), timeToInt(adv_time)
    
    time = [0 for _ in range(playTime + 1)]
    for log in logs:
        start, end = log.split('-')
        time[timeToInt(start)] += 1
        time[timeToInt(end)] -= 1
    
    sumTime = [0 for _ in range(playTime + 1)]
    curr = time[0]
    for i in range(1, playTime + 1):
        sumTime[i] += sumTime[i - 1] + curr
        curr += time[i]
    
    startTime, maxSum = 0, 0
    for i in range(playTime + 1 - advTime):
        if sumTime[i + advTime] - sumTime[i] > maxSum:
            maxSum = sumTime[i + advTime] - sumTime[i]
            startTime = i
    
    answer = intToTime(startTime)
    return answer

느낀점

저번에 푼 (내 기준 부분합 끝판왕 문제) [프로그래머스] 파괴되지 않는 건물을 보고 부분합이 떠올랐다. 이제 조금은 전에 푼 문제들을 응용할 수 있게 된 것 같아 기분이 좋았다.