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

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 이해 및 접근

초기에 모든 구현을 하는 방식으로 접근하였습니다.

그러나 변수의 범위가 매우 넓어 시간초과가 발생하였습니다.

 

이후에 시간 단축을 위하여 고민하던 중 시청자가 몇명인지에 따라 결과가 달라지기 때문에 누적합을 이용하여 풀이를 할 수 있다고 생각하여 접근했습니다.

2) 알고리즘

• 누적합

3) 풀이 코드

사용 언어 - Python

def solution(play_time, adv_time, logs):
    def time_to_seconds(s):                                         # 문자열 시간을 초로 바꾸어 주는 함수
        return int(s[:2]) * 3600 + int(s[3:5]) * 60 + int(s[6:8])

    play_time_seconds = time_to_seconds(play_time)                  # 영상 총 길이 초로 변환
    adv_time_seconds = time_to_seconds(adv_time)                    # 광고 시간 초로 변환
    watch_table = [0] * (play_time_seconds + 2)                     # 각 시간대별 시청자 수, 누적합 리스트
    max_play_time = 0                                               # 광고 이윤이 많이 남는 시간양
    answer = 0                                                      # 광고 이윤이 많이 남는 시작 시간
    
    for log in logs:                                                # 시청 기록들 하나씩 반복
        start, end = log.split('-')                                 # 시청 시작 시간, 종료 시간

        start_seconds = time_to_seconds(start)                      # 초로 변환
        end_seconds = time_to_seconds(end)

        watch_table[start_seconds + 1] += 1                         # 시청 시작 시간 인덱스에는 + 1
        watch_table[end_seconds + 1] -= 1                           # 시청 종료 시간 인덱스에는 - 1

    for _ in range(2):                                                  # 반복 1회 - 각 시간대별 몇명이 시청중인지 구하기
        for idx in range(1, play_time_seconds + 2):                     # 반복 2회 - 시간대별 시청중인 기록을 누적합으로 구하기
            watch_table[idx] = watch_table[idx-1] + watch_table[idx]
    
    for t in range(play_time_seconds-adv_time_seconds, -1, -1):             # 광고를 뒤에서부터 앞으로 탐색 시작
        tmp_play_time = watch_table[t+adv_time_seconds] - watch_table[t]    # 광고 이윤 시간 = 종료시 누적합 - 시작시 누적합
        if max_play_time <= tmp_play_time:                                  # 이윤이 같거나 더 많으면 새로 갱신
            max_play_time = tmp_play_time
            answer = t
            
    return f'{str(answer//3600).zfill(2)}:{str(answer%3600//60).zfill(2)}:{str(answer%60).zfill(2)}'    # 출력

---

📝 결과 및 학습한 내용

1) 어려웠던 내용

풀이를 위한 알고리즘 선택으로 누적합을 떠올리는게 쉽지 않았습니다.

2) 새롭게 학습한 내용

특별히 없습니다.

---

🔗 문제 링크

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

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

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다