[Programmers][Python]광고 삽입

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

📌풀이

내가 쓴 풀이(성공)

• time_to_sec : 00:00:00로 표기된 시간을 초로 변환
• sec_to_time: 초로 표기된 시간을 00:00:00의 형태로 변환
• DP를 활용하여 해결
• logs의 값들을 통해 시작 시간, 끝나는 시간을 확인하고, 초기화 한 리스트 times에 추가
  • 시작 시간 + 1, 끝나는 시간 -1
  • 모든 logs의 내용을 처리한 후, times의 값을 처음부터 읽으며 값을 누적시킴
• times의 시간들을 읽어가며, 최대값이 나타나는 구간을 확인
  • 그 때의 시작 값을 00:00:00의 형태로 리턴
  • 앞의 값을 빼주고, 뒤에 값을 더해주는 과정으로 진행

# 시간을 초로 변환
def time_to_sec(time):
    return int(time[:2])*3600 + int(time[3:5])*60 + int(time[6:])

# 초를 시간으로 변환
def sec_to_time(sec):
    hour, sec = sec//3600, sec%3600
    minute, sec = sec//60, sec%60
    hour = str(hour).rjust(2, '0') # 일의 자리인 경우를 고려
    minute = str(minute).rjust(2, '0')
    sec = str(sec).rjust(2,'0')
    return f'{hour}:{minute}:{sec}'

def solution(play_time, adv_time, logs):
    # 플레이 시간, 광고 시간을 초로 변환
    # 전체 플레이 시간 기준으로 dp 구현
    play_sec = time_to_sec(play_time)
    adv_sec = time_to_sec(adv_time)
    times = [0 for _ in range(play_sec+1)]
    
    # 시작점에 +1, 끝점에 -1 설정
    for log in logs:
        start, end = log[:8], log[9:]
        times[time_to_sec(start)] += 1
        times[time_to_sec(end)] -= 1
    
    # 앞서 설정한 값들을 기준으로, 해당 시간대의 총 재생기록 표시
    for idx in range(1, play_sec+1):
        times[idx] += times[idx-1]
    
    # 0초 기준으로 초기화
    now = sum(times[:adv_sec]) # 현재 누적 재생 시간
    result = now # 최대 누적 재생 시간
    answer = 0 # 최적의 위치
    for idx in range(1, play_sec+2-adv_sec) :
        now += times[idx+adv_sec-1]-times[idx-1] # 맨 앞 값 제거, 맨 뒤 값 추가
        if result < now : # 크기 비교
            answer, result = idx, now
                         
    return sec_to_time(answer)

📌후기

마지막의 최대 값을 구하는 과정에서, 처음에 sum을 다수 활용했었는데, 시간 초과 이슈가 발생했었다. 이러한 문제를 해결하고자, 인덱스를 이동하며 sum을 하는 과정을 앞의 값을 빼고, 뒤의 값을 더하는 방식으로 구현하였다. 전체적인 구조는 DP를 활용하여 잘 해결할 수 있었다.