[프로그래머스 level3 광고 삽입] 다이나믹 프로그래밍 활용하기

해결해야하는 문제는 다음과 같았다.

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

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

 

이 문제는 해결하는데 굉장히 오랜 시간이 걸렸다.

무작위로 시간을 탐색하다가, 약 8개정도의 테스트케이스에서 시간 초과가 났다.

계속 고민하던 결과,,,, 문제를 해결하지 못하여 질문하기 및 검색을 해보았다.

검색 결과, 누적 시간이 긴 경우를 찾는 것이기 때문에 다이나믹 프로그래밍을 해결하면 시간초과도 극복할 수 있고 결과를 도출할 수 있다는 것도 알 수 있었다.

 

(카카오에서 굉장히 자세하고 상세하게 이 문제를 해결해놓았다 !!!!! : https://tech.kakao.com/2021/01/25/2021-kakao-recruitment-round-1/ )

 

이 문제 접근 시, 핵심 방법은

1. 여느 시간 문제와 비슷하게, 시간을 초 단위로 바꾸어 해결하는 것

2. '누적' 재생 시간이므로, dp table을 생성하여 memozation 을 하는 것이다.

 

 

워낙 썼다 지웠다를 반복해서 굉장히 더러워졌다..ㅎㅎ

이러한 생각을 바탕으로 작성한 코드는 다음과 같다.

def solution(play_time, adv_time, logs):
    if play_time == adv_time :
        return '00:00:00'

    # convert hour ,minute to second
    play_time_list = play_time.split(':')
    play_time_second = int(play_time_list[0])*60*60 + int(play_time_list[1])*60 + int(play_time_list[2])

    adv_time_list = adv_time.split(':')
    adv_time_second = int(adv_time_list[0])*60*60 + int(adv_time_list[1])*60 + int(adv_time_list[2])

    # time, people 변화
    dp_time_people_stamp= [0 for i in range(play_time_second+1)]
    for i in logs :
        temp = i.split('-')
        start_time_list = temp[0].split(':')
        end_time_list = temp[1].split(':')

        start_time_second = int(start_time_list[0])*60*60 + int(start_time_list[1])*60 + int(start_time_list[2])
        end_time_second = int(end_time_list[0])*60*60 + int(end_time_list[1])*60 + int(end_time_list[2])

        dp_time_people_stamp[start_time_second]+=1
        dp_time_people_stamp[end_time_second]+=-1

    for i in range(1,play_time_second+1):
        dp_time_people_stamp[i] += dp_time_people_stamp[i-1]

    for i in range(1,play_time_second+1):
        dp_time_people_stamp[i] += dp_time_people_stamp[i-1]

    max_people = dp_time_people_stamp[adv_time_second]
    max_accum_time = 0
    for start_point in range(play_time_second-adv_time_second+1):
        if max_people < dp_time_people_stamp[start_point+adv_time_second]-dp_time_people_stamp[start_point] :
            max_people = dp_time_people_stamp[start_point+adv_time_second] - dp_time_people_stamp[start_point]
            max_accum_time = start_point+1


    hours = max_accum_time // 3600
    mins = (max_accum_time % 3600) // 60
    secs = max_accum_time % 60
    return '{:02d}:{:02d}:{:02d}'.format(hours, mins, secs)