[프로그래머스 2021 KAKAO BLIND RECRUITMENT: 광고 삽입] (Python)

문제링크 https://school.programmers.co.kr/learn/courses/30/lessons/72414

프로그래머스

문제 유형

• 구간합/누적합
• 투포인터 

 

문제 접근

• 시, 분, 초 단위 통일
  -> 초 단위로 통일한다
• 최대한 많은 시청자가 영상을 재생한 구간에 광고가 삽입되어야 함 
  -> 어떤 구간을 특정하기가 어려움 
  -> 모든 시간대 마다 시청자의 누적 재생 시간을 구해서 최대가 되는 구간을 찾는다.
• 누적합 알고리즘을 이용해 영상 재생 시간동안 각 시간별 시청자의 수를 구한다
  -> 0(N)으로 시간별 시청자 수를 계산할 수 있음 

 

풀이

1. 각 시간별 시청자수의 누적합을 위한 리스트 정의
2. 시청자의 시청 log마다 시작 시간 s는 누적합 리스트에 +1, 종료시간 e는 누적합 리스트에 -1 해준다 
3. 누적합 리스트를 처음부터 끝 인덱스까지 앞의 요소와 더해나가 누적합을 계산한다 
4. 0초부터 시작해 영상 끝까지 광고 구간길이 단위로 살펴보면서 시청자들의 누적 재생 시간이 가장 큰 곳을 찾아 리턴
   이때, 매번 슬라이싱으로 누적 시청자수를 구하지 말고 투포인터로 인덱스 하나씩 옮기면서 원소 제거, 추가 해주면서 시간 효율을 개선한다

 

코드

def solution(play_time, adv_time, logs):
    answer = 0
    if play_time == adv_time:
        return "00:00:00"
    
    h, m, s = map(int, adv_time.split(":"))
    adv_t = h*60*60 + m*60 + s
    ph, pm, ps = map(int, play_time.split(":"))
    play_t = ph*60*60 + pm*60 + ps 
    
    chart = [0]*(play_t+1) #누적합을 위한 리스트 
    for log in logs:
        start, end = log.split("-")
        sh, sm, ss = map(int, start.split(":"))
        eh, em, es = map(int, end.split(":"))
        start = sh*60*60 + sm*60 + ss #시각을 초단위로 변경
        end = eh*60*60 + em*60 + es
        chart[start] += 1 #시작인덱스에 +1
        chart[end] += -1 #종료인덱스에 -1 
    
    # 누적합 계산: 앞에서부터 원소를 순차적으로 뒤의 원소와 더해나간다 
    for i in range(1, play_t+1):
        chart[i] += chart[i-1]
    
    max_sum = sum(chart[:adv_t])
    tmp_sum = sum(chart[:adv_t])
    for i in range(1, play_t-adv_t+1): #모든 시간구간을 살펴보기 
        tmp_sum -= chart[i-1]
        tmp_sum += chart[i+adv_t-1]
        if tmp_sum > max_sum: #최대값보다 해당 구간의 값이 크면 answer 갱신 
            answer = i 
            max_sum = tmp_sum 
            
    h, m, s = (answer//3600), (answer//60)%60, answer%60
    return "%02d:%02d:%02d"%(h,m,s) #2자리수인데, 공백에 0을 채우기