[ 프로그래머스 / LV3 / 파이썬 Python ] 광고 삽입

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

프로그래머스

 

코드

---

# 초를 시간으로 변경
def numToTime(sec):
    h = sec // (60 * 60)
    sec %= (60 * 60)
    m = sec // 60
    sec %= 60
    s = sec
    return '%02d:%02d:%02d' % (h, m, s)
   
# 시간을 초로 변경
def timeToNum(time):
    h,m,s = map(int,time.split(':'))
    return h*3600 + m*60 + s

def solution(play_time, adv_time, logs):
    answer = numToTime(0)
    play_time, adv_time = timeToNum(play_time), timeToNum(adv_time)
    
    # 누적합으로 초마다 인원수 계산
    res = [0] * (play_time+1)
    for log in logs:
        start,end = map(timeToNum,log.split("-"))
        res[start] += 1
        res[end] -= 1      
    for i in range(1,play_time+1):
        res[i] += res[i-1]
    
    # 투포인터를 이용해 최대값 및 정답 갱신
    left = 0
    MAX = total = sum(res[:adv_time])
    for t in range(adv_time,play_time+1):
        total -= res[left]
        total += res[t]
        left += 1
        if total > MAX:
            answer = numToTime(left)
            MAX = total
            
    return answer

 

풀이

---

요즘 이런 시간에 관련된 문제들을 많이 풀어보고 있는 것 같다. 이번 문제에서는 시간, 분, 초가 주어졌기 때문에 가장 작은 단위인 초를 기준으로 변환하였다. 근데 정말 어렵다...

 

문제의 해결 아이디어는 다음과 같다.

• 99시간59분59초라는 최대값을 초로 변환하여도 360000정도밖에 되지 않기 때문에 초를 인덱스로 삼는 배열을 생성한다.
• 재생시간이 해당 시간에 시청중인 시청자의 수에 비례하므로 초마다 시청중인 시청자의 수를 저장한다.
  • 누적합을 이용한다.
  • 시작 시간 += 1, 끝나는 시간 += -1을 해주면 누적합을 진행한 후에 해당 초에 시청중인 시청자의 수가 저장되어 있다.
• 누적합이 시행된 배열을 광고재생시간 단위로 탐색하며 최대값을 갱신한다.
  • 시간복잡도를 줄이기 위해 슬라이딩 윈도우 + 투포인터를 사용하였다.
  • 초기값을 00:00:00 ~ 광고재생시간으로 잡고 그 이후부터는 1초씩 더해가며 누적재생시간을 갱신하였다.