광고삽입

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

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

비효율적으로....

def solution(play_time, adv_time, logs):
    play_seconds = time_to_seconds(play_time)
    adv_seconds = time_to_seconds(adv_time)
    played = [0] * play_seconds
    for log in logs:
        log_start, log_end = map(time_to_seconds, log.split('-'))
        for each in range(log_start, log_end):
            played[each] += 1
    adv_start, max_total = 0, 0
    for start in range(play_seconds - adv_seconds + 1):
        total = 0
        for each in range(start, start + adv_seconds):
            total += played[each]
        if max_total < total:
            adv_start = start
            max_total = total
    return seconds_to_time(adv_start)


def time_to_seconds(time):
    return int(time[0:2]) * 3600 + int(time[3:5]) * 60 + int(time[6:8])


def seconds_to_time(seconds):
    s = seconds % 60
    seconds //= 60
    m = seconds % 60
    seconds //= 60
    h = seconds
    return f'{h:02d}:{m:02d}:{s:02d}'

투 포인트를 이용해서.. 

def solution(play_time, adv_time, logs):
    play_seconds = time_to_seconds(play_time)
    adv_seconds = time_to_seconds(adv_time)
    time_table = [0] * (play_seconds + 1)
    for log in logs:
        log_start, log_end = map(time_to_seconds, log.split('-'))
        for each in range(log_start, log_end):
            time_table[each] += 1
    adv_start, max_total = 0, 0
    total = sum(time_table[:adv_seconds])
    for start in range(play_seconds - adv_seconds + 1):
        if max_total < total:
            adv_start = start
            max_total = total
        total += time_table[start + adv_seconds] - time_table[start]
    return seconds_to_time(adv_start)


def time_to_seconds(time):
    return int(time[0:2]) * 3600 + int(time[3:5]) * 60 + int(time[6:8])


def seconds_to_time(seconds):
    s = seconds % 60
    seconds //= 60
    m = seconds % 60
    seconds //= 60
    h = seconds
    return f'{h:02d}:{m:02d}:{s:02d}'

조금 더 최적화

def solution(play_time, adv_time, logs):
    play_seconds = time_to_seconds(play_time)
    adv_seconds = time_to_seconds(adv_time)
    played = [0] * (play_seconds + 1)
    for log in logs:
        log_start, log_end = map(time_to_seconds, log.split('-'))
        played[log_start] += 1
        played[log_end] -= 1
    for index in range(1, play_seconds + 1):
        played[index] += played[index - 1]
    adv_start, max_total = 0, 0
    total = sum(played[:adv_seconds])
    for start in range(play_seconds - adv_seconds + 1):
        if max_total < total:
            adv_start = start
            max_total = total
        total += played[start + adv_seconds] - played[start]
    return seconds_to_time(adv_start)


def time_to_seconds(time):
    return int(time[0:2]) * 3600 + int(time[3:5]) * 60 + int(time[6:8])


def seconds_to_time(seconds):
    s = seconds % 60
    seconds //= 60
    m = seconds % 60
    seconds //= 60
    h = seconds
    return f'{h:02d}:{m:02d}:{s:02d}'