[Programmers] 광고 삽입

🎯 programmers > 2021 KAKAO BLIND RECRUITMENT > 광고 삽입

---

🤔 나의 풀이

📌 문제

- programmers > 2021 KAKAO BLIND RECRUITMENT > 광고 삽입

📌 날짜

2021.06.26

📌 시도 횟수

Failed

---

🏆 문제 해결 방법

• 이 블로그를 참고해서 풀었다. (정말 감사합니다...🙇‍♀️)
• 이 문제의 핵심은 바로 DP (동적계획법)이다.
  그 중에서 특히 memoization으로 푸는 문제이다👀

👊🏻 문제 해결 방법을 이해해보자.

1. 초(second)로 변환해서 계산하기

• 문제에서 주어진 시간은 HH:MM:SS 형태의 문자열이다. 시간 자체가 연산이 쉽지 않은 데에다 문자열이어서 더더욱 계산이 복잡하고 어렵다.
• 그런데 이게 웬걸?! 문제에서 HH:MM:SS의 범위를 주었다.
  
• 이러면 얘기가 달라지지...😎
  즉, 전체 동영상 재생 시간은 아무리 길어봤자 99:59:59를 넘지 않는다는 말이고, 99:59:59는 초(second)로 변환하면 359999초 이다.
• 즉 0초까지 포함한다면, 문제에서 나올 수 있는 모든 시각의 개수는 360000개를 넘지 않는다. 휴... 이때부터 DP인걸 알아차렸어야 됐는데...

# 시간(HH:MM:SS)을 초(sec)로 변환하기
def time_to_seconds(time):
    hour, minute, second = map(int, re.sub(":", " ", time).split())
    return hour * 60 * 60 + minute * 60 + second

# 초(sec)를 다시 시간(HH:MM:SS)으로 변환하기
def seconds_to_time(seconds):
    second = seconds % 60
    seconds //= 60
    minute = seconds % 60
    seconds //= 60
    hour = seconds

    # zfill(int) : 문자열 앞을 0으로 채워준다.
    return str(hour).zfill(2) + ":" + str(minute).zfill(2) + ":" + str(second).zfill(2)

---

2. 전체 동영상 재생길이의 초(sec)를 크기로 갖는 리스트 time_log 만들기

• 따라서 우선 크기가 전체 동영상 재생시간 길이 play_time의 초(sec)인 리스트 time_log를 만든다.

# time_log = 배열의 크기가 전체 동영상 재생시간의 길이의 초(sec)인 리스트
time_log = [0 for _ in range(total_play_sec + 1)]

• 🐢예시 (20초짜리 동영상이 있다고 가정하면 이렇게 만들어지겠죠?)

---

3. time_log에, 해당 초(sec)에서의 시청자 수 기록하기

• 이제 time_log의 각 초(sec)에, 해당 초(sec)에서의 시청자 수를 기록한다.
• 이것도 효율적으로 기록하는 방법이 있다.
• 우선 logs의 H1:M1:S1-H2:M2:S2를 초(sec)로 변환한 것을 start - end라고 하면,
  time_log[start]에는 +1 값을, time_log[end]에는 -1 값을 더해준다.
• 이렇게 logs의 시작점, 끝점을 time_log에 모두 표시해준 뒤에
  time_log[i] = time_log[i] + time_log[i - 1]를 통해 현재 초(sec)에서의 시청자 수를 기록해줄 수 있다.

    # start에는 +1, end에는 -1 마킹해주기
    for log in logs:
        start, end = re.sub("-", " ", log).split()
        start_sec = time_to_seconds(start)
        end_sec = time_to_seconds(end)
        time_log[start_sec] += 1
        time_log[end_sec] -= 1
 
    # 현재 초(sec)에서의 시청자 수 기록하기
    for i in range(1, total_play_sec):
        time_log[i] = time_log[i] + time_log[i - 1]

• 🐢예시

---

4. 이제 memoization으로 0부터 현재 초(sec)까지의 누적 시청자 수를 기록한다.

• time_log[i] = time_log[i] + time_log[i - 1] 를 한번 더 해주면 현재 시간(i)에 대하여 0초 ~ i초 까지의 누적 시청자 수를 time_log에 기록할 수 있다.

    # 0초 ~ i초 까지의 누적 시청자 수 기록
    for i in range(1, total_play_sec + 1):
        time_log[i] = time_log[i] + time_log[i - 1]

• 예시(파란색)

---

5. 최종적으로 시청자 수가 가장 많은, 즉 누적 재생 시간이 가장 큰 구간을 탐색한다.

• total_adv_sec : 광고 시간을 초(sec)로 변환한 값이다.
• 반복문을 돌며 시각 i-total_adv_sec ~ i에 광고를 넣을 때의 누적 재생 시간을 구하여, 그중에서 가장 긴 시간을 max_view에 저장하여 갱신한다.
• 갱신할 때는 max_view = time_log[i] - time_log[i - total_adv_sec]로 갱신하고, max_view_start에는 해당 max_view 구간에서의 시작 시간을 저장한다.

    max_view = time_log[total_adv_sec - 1] - time_log[0]
    max_view_start = 0

    for i in range(total_adv_sec, total_play_sec):
        if max_view < time_log[i] - time_log[i - total_adv_sec]:
            max_view = time_log[i] - time_log[i - total_adv_sec]
            max_view_start = i - total_adv_sec + 1

• 🐢예시 (슬라이딩 윈도우를 알면 이해가 쉽다)
  

---

✅ 최종 코드 (정확성 100)

import re


def time_to_seconds(time):
    hour, minute, second = map(int, re.sub(":", " ", time).split())
    return hour * 60 * 60 + minute * 60 + second


def seconds_to_time(seconds):
    second = seconds % 60
    seconds //= 60
    minute = seconds % 60
    seconds //= 60
    hour = seconds

    return str(hour).zfill(2) + ":" + str(minute).zfill(2) + ":" + str(second).zfill(2)


def solution(play_time, adv_time, logs):
    total_play_sec = time_to_seconds(play_time)
    total_adv_sec = time_to_seconds(adv_time)
    time_log = [0 for _ in range(total_play_sec + 1)]

    for log in logs:
        start, end = re.sub("-", " ", log).split()
        start_sec = time_to_seconds(start)
        end_sec = time_to_seconds(end)
        time_log[start_sec] += 1
        time_log[end_sec] -= 1

    for i in range(1, total_play_sec):
        time_log[i] = time_log[i] + time_log[i - 1]

    for i in range(1, total_play_sec + 1):
        time_log[i] = time_log[i] + time_log[i - 1]

    max_view = time_log[total_adv_sec - 1] - time_log[0]
    max_view_start = 0

    for i in range(total_adv_sec, total_play_sec):
        if max_view < time_log[i] - time_log[i - total_adv_sec]:
            max_view = time_log[i] - time_log[i - total_adv_sec]
            max_view_start = i - total_adv_sec + 1

    return seconds_to_time(max_view_start)

---

🐢 느낀점

이 문제 푸는데 삽질만 3시간했다....🥺
계속 '좀만 고치면 될 거 같은데..?!' 하면서 꾸역꾸역 풀었더니
나중에는 정말 무시무시한 코드(가독성 -999999)가 됐다 :)

해설을 보니까 생각보다 엄청 어렵지 않아서
내가 왜 이렇게 생각을 못했지??하는 생각이 드는
많이 아쉬움이 남는 문제인 거 같다🥺