[프로그래머스] 72414번 문제 2021 KAKAO BLIND RECRUITMENT 광고 삽입

def changeSeconds(times):
    return  sum(int(x) * 60 ** i for i, x in enumerate(reversed(times.split(':'))))
def changeString(times):
    hour = times//3600
    minute = (times-hour*3600)//60
    seconds = times%60
    return "%02d:%02d:%02d"%(hour,minute,seconds)
 
def solution(play_time, adv_time, logs):
    answer = ''
    play_time =  changeSeconds(play_time)
    adv_time = changeSeconds(adv_time)
    time_laps = [0]*(play_time+1)
    for timeString in logs:
        start_time,end_time = map(changeSeconds, timeString.split('-'))
        time_laps[start_time] += 1
        time_laps[end_time] -= 1
 
    for ind in range(1,play_time+1):
        time_laps[ind] += time_laps[ind-1]
    max_times = sum(time_laps[:adv_time])
    max_start_time = 0
    current_sum_times = max_times
    for ind in range(1,play_time+1-adv_time):
        current_sum_times = current_sum_times - time_laps[ind-1] + time_laps[ind+adv_time-1]
        if current_sum_times > max_times:
            max_times = current_sum_times
            max_start_time = ind
    answer = changeString(max_start_time)
    return answer

구간합을 이용해 푼 방식이다.

각 start와 end_time에 각각 +1, -1을 해주고,

 

누적값을 해준다. 그리고 그 광고시간의 길이만큼의 sum을 해주면, 해당 시간동안 보는 광고사용자의 수가 될수 있다.

 

 

def changeSeconds(times):
    return  sum(int(x) * 60 ** i for i, x in enumerate(reversed(times.split(':'))))
def changeString(times):
    hour = times//3600
    minute = (times-hour*3600)//60
    seconds = times%60
    return "%02d:%02d:%02d"%(hour,minute,seconds)
 
def solution(play_time, adv_time, logs):
    answer = ''
    play_time =  changeSeconds(play_time)
    adv_time = changeSeconds(adv_time)
    time_laps = [0]*(play_time+1)
    diff = [0]*(play_time+1)
    for timeString in logs:
        start_time,end_time = map(changeSeconds, timeString.split('-'))
        diff[start_time] += 1
        diff[end_time] -= 1
    diff_count = 0
    for ind in range(1,play_time+1):
        time_laps[ind] += time_laps[ind-1] + diff_count
        diff_count += diff[ind]
 
    max_times = time_laps[adv_time]
    max_start_time = 0
    for ind in range(1,play_time+1-adv_time):
        if time_laps[adv_time+ind] - time_laps[ind] > max_times:
            max_times = time_laps[adv_time+ind] - time_laps[ind]
            max_start_time = ind
    answer = changeString(max_start_time)
    return answer

 

같은 원리이지만, sum 하는 방식을 개선을 한것이다. diff_count를 해줘서 해당구간에서 보는 인원을 누적해줘서 하는 방식이다.