광고 삽입 (72414번) - 프로그래머스 (Programmers)

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

프로그래머스

 

 

프로그래머스 - 광고 삽입 (72414번)

 

난이도 : Lv 3

알고리즘 : Prefix Sum (누적 합)

풀이 소요 시간 : 100 mins

 

 

def ttos(x):
    h, m, s = map(int, x.split(':'))
    return h*3600 + m*60 + s


def solution(play, adv, logs):
    play = ttos(play)
    adv = ttos(adv)
    memo = [0] * (play+1)    
    for log in logs:
        s, e = log.split('-')
        memo[ttos(s)] += 1
        memo[ttos(e)] -= 1
    
    for i in range(play):
        memo[i+1] += memo[i]
    
    cur = sum(memo[:adv])
    maxy = (0, cur)
    for i in range(play-adv):
        cur += memo[i+adv] - memo[i]
        if maxy[1] < cur:
            maxy = (i+1, cur)
    
    h, maxy = divmod(maxy[0], 3600)
    m, s = divmod(maxy, 60)
    return ':'.join(map(lambda x: str(x).rjust(2, '0'), (h, m, s)))

 

 

누적 합을 활용하는 문제이다.

 

---

 

 

 

① "HH:MM:SS" 형태의 시간을 초 단위 int로 변환한다.

 

 

② 0으로 초기화 된, (play_time + 1) 길이의 리스트 "memo"를 만든다.

 

 

③ logs의 각 log에 대해,

시작시간 s → memo[s] += 1
종료시간 e → memo[e] -= 1

작업을 진행한다.

 

 

④ memo의 앞에서부터 차례대로 누적합을 구해준다.

for i in range(play_time):
        memo[i+1] += memo[i]

 

 

⑤ memo의 앞에서부터

adv_time 길이만큼의 구간 합을 계산하고,

그 중 값이 가장 크면서 시작 시간이 가장 빠른 값을 출력한다.