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

이 풀이를 읽기 전 태상이의 훈련소 생활 문제를 푸시는 것을 추천드립니다(풀이:https://bjwan-career.tistory.com/4)

 

풀이

• "재생 시간을 간단하게 구하는 방법이 없을까?" 

10:43:20 ~ 12:22:57의 재생 시간을 원본 문자열 그대로 구하려면 상당히 힘들다. 
한 가지 방법은 초로 통일하여 계산하면 간단하게 재생 시간을 구할 수 있다.
또한 다른 이점은 구간을 나눠서 재생 시간을 계산하지 않아도 된다. 해당 초에 몇 명이 봤는지 알 수 있다면 최종 재생시간을 구할 수 있다.

• '해당 초에 몇 명이 동영상을 시청하고 있다'를 빠르게 구할 수 있는 방법은 없을까?"

누적합을 사용하면 해당 초에 몇 명이 시청하는지 알 수 있다
동영상의 시작 부분과 종료 시간을 초로 변경한 후 해당 시간을 index로 arr[start_sec] += 1,  arr[end_sec] -= 1 계산한다.
해당 배열로 누적합을 구한다면 start_sec부터는 +1로 증가되여 누적합이 계산될 것이고 종료 부분에는 -1을 만나므로 start_sec에서 +1 더한 값이 소멸될 것이다.

def sum_watching_player(psum_of_time, logs):

    for log in logs:
        start_time, end_time = map(chagne_time_to_sec, log.split("-"))

        psum_of_time[start_time] = psum_of_time[start_time] + 1
        psum_of_time[end_time] = psum_of_time[end_time] -1

	#누적합을 이용해 n2이 필요하던 부분을 n으로 변경함
    for i in range(1, len(psum_of_time)):
        psum_of_time[i] = psum_of_time[i] + psum_of_time[i - 1]

• "어디에서 시작하면 빠를까"

이 부분은 0초에서 시작하면 된다. 최대 100시간이기 때문에 초로 변환하면 360,000만이고 O(n) 알고리즘에서는 충분한 동작 시간을 확보할 수 있기 때문이다.
 
우리는 모든 시간을 초로 변환했기 때문에 다시 누적합을 이용할 수 있다. 누적합의 장점은 특정 구간을 빠르게 구할 수 있다는 것이다. 다시 말하지만 이는 시간을 초로 변환했기 때문에 가능한 것이다. 

#처음 총 광고 시간을 구한다
for i in range(1, adv_time_sec):
    max_watching_time += psum_of_time[i-1]

watching_time = max_watching_time

#이후에는 1초씩씩 재생하면서 앞에서 구한 광고 시간까지 몇 명이 보는지 추가한다. 
#또한 1초를 재생했음으로 [i - adv_time_sec - 1] 해당 시간에 시청하던 사람은 빼야한다. 
for i in range(adv_time_sec, len(psum_of_time)):
    watching_time = watching_time + psum_of_time[i - 1] - psum_of_time[i - adv_time_sec - 1]

    if max_watching_time < watching_time:
        max_watching_time = watching_time
        start_time_sec = i - adv_time_sec

코드

def chagne_time_to_sec(time):
    h, m, s = map(int, time.split(":"))

    return h * 3600 + m * 60 + s

def change_sec_to_time(sec):
    m, s = divmod(sec, 60)
    h, m = divmod(m, 60)

    h, m, s = map(str, [h,m,s])

    h = h.zfill(2)
    m = m.zfill(2)
    s = s.zfill(2)

    time = ":".join([h,m,s])
    return  time



def sum_watching_player(psum_of_time, logs):

    for log in logs:
        start_time, end_time = map(chagne_time_to_sec, log.split("-"))

        psum_of_time[start_time] = psum_of_time[start_time] + 1
        psum_of_time[end_time] = psum_of_time[end_time] -1


    for i in range(1, len(psum_of_time)):
        psum_of_time[i] = psum_of_time[i] + psum_of_time[i - 1]

def solution(play_time, adv_time, logs):
    answer = ''

    play_time_sec = chagne_time_to_sec(play_time)
    psum_of_time = [0] * (play_time_sec + 1)

    adv_time_sec = chagne_time_to_sec(adv_time)

    sum_watching_player(psum_of_time, logs)

    max_watching_time = 0
    watching_time = 0
    start_time_sec = 0

    for i in range(1, adv_time_sec):
        max_watching_time += psum_of_time[i-1]

    watching_time = max_watching_time
        
    for i in range(adv_time_sec, len(psum_of_time)):
        watching_time = watching_time + psum_of_time[i - 1] - psum_of_time[i - adv_time_sec - 1]

        if max_watching_time < watching_time:
            max_watching_time = watching_time
            start_time_sec = i - adv_time_sec

    start_time = change_sec_to_time(start_time_sec)

    return start_time




if __name__ == "__main__":
    play_time = "99:59:59"
    adv_time = "25:00:00"
    logs = ["69:59:59-89:59:59", "01:00:00-21:00:00", "79:59:59-99:59:59", "11:00:00-31:00:00"]

    print(solution(play_time, adv_time, logs))

후기

숨이 탁탁 막히는 문제였다. 어떻게 하면 시간을 쉽게 계산해줄지, 어느 부분부터 계산하는 것이 빠를지, 해당 부분에 몇 명이 보고 있는지 알 수 있는 방법들....

 

처음부터 명확한 답이 생각나면 좋겠지만, 대부분 그렇지 못하다. 쉬운 풀이부터 생각하고 점진적으로 개선하면 풀 수 있다. 절대 귀찮아하지 말기