[프로그래머스] 광고 삽입 (2021 KAKAO BLIND) / python

1. 문제 설명

프로그래머스

[문제]

"죠르디"의 동영상 재생시간 길이 play_time, 공익광고의 재생시간 길이 adv_time, 시청자들이 해당 동영상을 재생했던 구간 정보 logs가 매개변수로 주어질 때, 시청자들의 누적 재생시간이 가장 많이 나오는 곳에 공익광고를 삽입하려고 합니다. 이때, 공익광고가 들어갈 시작 시각을 구해서 return 하도록 solution 함수를 완성해주세요. 만약, 시청자들의 누적 재생시간이 가장 많은 곳이 여러 곳이라면, 그 중에서 가장 빠른 시작 시각을 return 하도록 합니다.

[제한사항]

• play_time, adv_time은 길이 8로 고정된 문자열입니다.
  • play_time, adv_time은 HH:MM:SS 형식이며, 00:00:01 이상 99:59:59 이하입니다.
  • 즉, 동영상 재생시간과 공익광고 재생시간은 00시간 00분 01초 이상 99시간 59분 59초 이하
  • 공익광고 재생시간은 동영상 재생시간보다 짧거나 같게 주어집니다.
• logs는 크기가 1 이상 300,000 이하인 문자열 배열입니다.
  • logs 배열의 각 원소는 시청자의 재생 구간을 나타냅니다.
  • logs 배열의 각 원소는 길이가 17로 고정된 문자열입니다.
  • logs 배열의 각 원소는 H1:M1:S1-H2:M2:S2 형식입니다.
    • H1:M1:S1은 동영상이 시작된 시각, H2:M2:S2는 동영상이 종료된 시각을 나타냅니다.
    • H1:M1:S1는 H2:M2:S2보다 1초 이상 이전 시각으로 주어집니다.
    • H1:M1:S1와 H2:M2:S2는 play_time 이내의 시각입니다.
• 시간을 나타내는 HH, H1, H2의 범위는 00~99, 분을 나타내는  MM, M1, M2의 범위는 00~59, 초를 나타내는 SS, S1, S2의 범위는 00~59까지 사용됩니다. 잘못된 시각은 입력으로 주어지지 않습니다. (예: 04:60:24, 11:12:78, 123:12:45 등)
• return 값의 형식
  • 공익광고를 삽입할 시각을 HH:MM:SS 형식의 8자리 문자열로 반환합니다.

 

2. 풀이 전 계획과 생각

HashMap

전체 시간에 대한 count Map 만드는데, 시간초과가 난다.

 

HashMap, TwoPointer

구간의 첫시간, 끝시간 대한 count Map 만드는데도 시간초과가 난다.

구간마다 각 구간사이의 시간을 탐색하여 count를 처리해줘야 해서 번거롭다.

시청자들의 누적 재생시간이 가장 많이 나오는 곳을 찾기 위해서는 구간마다 합 처리가 필요하다.

구간합으로 접근해보자.

 

Prefix Sum (카카오 해설 참고)

 

3. 풀이

def time_to_sec(time):
    time = list(map(int, time.split(':')))
    return time[0] * 60 * 60 + time[1] * 60 + time[2]

def sec_to_time(time):
    result, x = [], 3600
    for i in range(3):
        result.append(str(int(time//x)).zfill(2))
        time %= x
        x /= 60
    return ':'.join(result)

def solution(play_time, adv_time, logs):
    play_time_sec = time_to_sec(play_time)
    adv_time_sec = time_to_sec(adv_time)
    
    # 영상의 초당 시청자 수
    time_to_total =  [0 for i in range(play_time_sec + 1)]

    # 각 구간의 시청자 수를 check 해주자
    # time_to_total[time] = time 시간에 시작된 시청자수 - time 시간에 종료된 시청자 수
    for log in logs:
        start, end = log.split('-')
        start = time_to_sec(start)
        end = time_to_sec(end)
        # start(초)에 시청자 1명 증가
        time_to_total[start] += 1 
        # end(초)에 시청자 1명 감소
        time_to_total[end] -= 1 

    # time_to_total[time] = time 시간부터 time + 1 시간까지 1초간의 구간을 포함한 시청자 수
    for i in range(1, len(time_to_total)):
        time_to_total[i] += time_to_total[i - 1]
    
    # time_to_total[time] = 0초 부터 time + 1 시간까지 구간을 포함한 누적 시청자 수
    for i in range(1, len(time_to_total)):
        time_to_total[i] += time_to_total[i - 1]
    
    answer = 0
    max_total = time_to_total[adv_time_sec - 1] # 0초부터 광고를 했을때 누적 시청자 수
    for current_time_sec in range(0, len(time_to_total) - adv_time_sec):
        # 현재 구간의 시청자 수의 max 갱신
        if time_to_total[current_time_sec + adv_time_sec] - time_to_total[current_time_sec] > max_total: 
            max_total = time_to_total[current_time_sec + adv_time_sec] - time_to_total[current_time_sec]
            answer = current_time_sec + 1

    return sec_to_time(answer)

 

4. 풀이 후 알게된 개념과 소감

• 구간이 나오면 투포인터 뿐만 아니라, 누적합으로도 접근해보자. 위의 문제는 구간의 누적 시청자수를 구해야 하므로 누적합으로 접근해볼 수 있다.
• 시청자들의 누적 재생시간을 구해주는 문제다. 누적 재생시간을 구하기 위해서 누적합을 활용하는데, 한번에 누적합 배열이 구해지지 않아서, 이 접근을 제외시켰다. 한번에 누적합 배열이 구해지지 않는다고 해서, 접근을 못하는 것이 아니다.
• 각 시작 시간과 종료 시간을 체크하고 이에 대한 누적합을 사용하여, time 시간부터 time + 1 시간까지 1초간의 구간을 포함한 시청자 수의 배열을 정의하고 이에 대한 누적합을 사용하여, 0초 부터 time + 1 시간까지 구간을 포함한 누적 시청자 수의 배열을 정의할 수 있었다. 누적합을 여러번 함으로써 누적합 배열을 재정의할 수 있다.