Level 3 광고 삽입 <2021 KAKAO BLIND RECRUITMENT> Python 3

https://programmers.co.kr/learn/courses/30/lessons/72414?language=python3 

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

 

최종 코드

• Github -> https://github.com/hwayeon351/Programmers-Algorithms/blob/main/level3_광고삽입.py

GitHub - hwayeon351/Programmers-Algorithms: 프로그래머스 알고리즘 소스 코드 모음

from collections import defaultdict
def solution(play_time, adv_time, logs):
    if play_time == adv_time: return '00:00:00'

    answer_sec = 0
    answer_total_sec = 0
    #counter[sec] = sec ~ sec+1까지 1초 동안의 시청자 수
    counter = defaultdict(int)
    for l in logs:
        time = l.split('-')
        t1 = list(map(int, time[0].split(':')))
        t2 = list(map(int, time[1].split(':')))
        s1 = t1[0]*3600 + t1[1]*60 + t1[2]
        s2 = t2[0]*3600 + t2[1]*60 + t2[2]
        counter[s1] += 1
        counter[s2] -= 1

    play_time = list(map(int, play_time.split(':')))
    play_sec = play_time[0]*3600 + play_time[1]*60 + play_time[2]
    adv_time = list(map(int, adv_time.split(':')))
    adv_sec = adv_time[0]*3600 + adv_time[1]*60 + adv_time[2]
    
    for sec in range(0, play_sec):
        counter[sec] += counter[sec-1]
        
    for sec in range(0, play_sec):
        counter[sec] += counter[sec-1]
    
    for i in range(adv_sec-1, play_sec):
        if i < adv_sec: total_sec = counter[i]
        else: total_sec = counter[i] - counter[i-adv_sec] 
        if total_sec > answer_total_sec:
            answer_total_sec = total_sec
            answer_sec = i
            
    answer_sec -= (adv_sec - 1)
    hh = str(answer_sec//3600).zfill(2)
    answer_sec %= 3600
    mm = str(answer_sec//60).zfill(2)
    ss = str(answer_sec%60).zfill(2)
    
    return hh+':'+mm+':'+ss

---

풀이 과정

from collections import defaultdict
def solution(play_time, adv_time, logs):
	#동영상 재생시간 길이와 공익광고 재생길이가 같으면 처음부터 광고를 실행하는 것이 가장 광고 누적 재생시간이 많이 나온다
    if play_time == adv_time: return '00:00:00'
	
    #answer_sec = 공익광고 시작 시간, answer_total_sec = 광고 누적 재생시간
    answer_sec = 0
    answer_total_sec = 0
    
    #counter[sec] = sec ~ sec+1까지 1초 동안의 시청자 수
    counter = defaultdict(int)
    
    for l in logs:
        time = l.split('-')
        t1 = list(map(int, time[0].split(':')))
        t2 = list(map(int, time[1].split(':')))
        
        #시작 시간과 종료 시간 초로 환산
        s1 = t1[0]*3600 + t1[1]*60 + t1[2]
        s2 = t2[0]*3600 + t2[1]*60 + t2[2]
        
        #시작 시간~시작 시간+1에 시청자수 +1 카운팅
        counter[s1] += 1
        #종료 시간~종료 시간+1에 시청자수 -1 카운팅
        counter[s2] -= 1

	#동영상 재생시간 길이 초로 환산
    play_time = list(map(int, play_time.split(':')))
    play_sec = play_time[0]*3600 + play_time[1]*60 + play_time[2]
    #공익광고 재생시간 길이 초로 환산
    adv_time = list(map(int, adv_time.split(':')))
    adv_sec = adv_time[0]*3600 + adv_time[1]*60 + adv_time[2]
    
    #sec~sec+1에 누적 재생시간 카운팅
    for sec in range(0, play_sec):
        counter[sec] += counter[sec-1]
    
    #0~sec+1에 누적 재생시간 카운팅
    for sec in range(0, play_sec):
        counter[sec] += counter[sec-1]
    
    #i-adv_sec~i까지 누적 재생시간 구하기
    for i in range(adv_sec-1, play_sec):
        if i < adv_sec: total_sec = counter[i]
        else: total_sec = counter[i] - counter[i-adv_sec] 
        
        #누적 재생시간이 최대인 값으로 갱신한다 
        if total_sec > answer_total_sec:
            answer_total_sec = total_sec
            answer_sec = i
    
    #정답 초로 환산
    answer_sec -= (adv_sec - 1)
    hh = str(answer_sec//3600).zfill(2)
    answer_sec %= 3600
    mm = str(answer_sec//60).zfill(2)
    ss = str(answer_sec%60).zfill(2)
    
    return hh+':'+mm+':'+ss
    
    #시간복잡도 = O(n), 공간복잡도 = O(n)