카카오 2021 기출 - 광고삽입

실패1

def strToTime(str):
    str = str.split(':')
    return int(str[0]) * 3600 + int(str[1]) * 60 + int(str[2])

def timeToStr(time):
    h = time // 3600
    time = time % 3600
    m = time // 60
    sec = time % 60
    return f'{h:0{2}d}:{m:0{2}d}:{sec:0{2}d}'


def solution(play_time, adv_time, logs):
    play_time = strToTime(play_time)
    adv_time = strToTime(adv_time)
    timeArr = [0] * play_time
    logs = list(map(lambda x: x.split('-'), logs))
    for i in range(len(logs)):
        logs[i][0] = strToTime(logs[i][0])
        logs[i][1] = strToTime(logs[i][1])
    for i in logs:
        for j in range(i[0], i[1]):
            timeArr[j] += 1
    logs = sorted(logs, key = lambda x:  x[0])

    maxNum = 0
    answer = 0
    for start, end in logs:
        count = sum(timeArr[start:start+adv_time])
        if maxNum < count :
            maxNum = count
            answer = start
    remainTime = adv_time - (play_time - answer)
    if remainTime > 0 :
        answer -= remainTime
    return timeToStr(answer)

시간초과... 두포인터를 활용해서 더해보기로 했다.

실패2

def strToTime(str):
    str = str.split(':')
    return int(str[0]) * 3600 + int(str[1]) * 60 + int(str[2])

def timeToStr(time):
    h = time // 3600
    time = time % 3600
    m = time // 60
    sec = time % 60
    return f'{h:0{2}d}:{m:0{2}d}:{sec:0{2}d}'


def solution(play_time, adv_time, logs):
    play_time = strToTime(play_time)
    adv_time = strToTime(adv_time)
    timeArr = [0] * play_time
    logs = list(map(lambda x: x.split('-'), logs))
    for i in range(len(logs)):
        logs[i][0] = strToTime(logs[i][0])
        logs[i][1] = strToTime(logs[i][1])
    for i in logs:
        for j in range(i[0], i[1]):
            timeArr[j] += 1
    logs = sorted(logs, key = lambda x:  x[0])

    maxNum = 0
    count = sum(timeArr[:adv_time])
    answer = 0
    l, r = 0, adv_time
    while r < play_time :
        count = count - timeArr[l] + timeArr[r]
        r += 1
        l += 1

        if count > maxNum :
            maxNum = count
            answer = l
    remainTime = adv_time - (play_time - answer)
    if remainTime > 0 :
        answer -= remainTime
    return timeToStr(answer)

print(solution(		"99:59:59", "25:00:00", ["69:59:59-89:59:59", "01:00:00-21:00:00", "79:59:59-99:59:59", "11:00:00-31:00:00"]))
print(solution("00:00:20", "00:00:05",["00:00:14-00:00:18", "00:00:01-00:00:05", "00:00:02-00:00:06", "00:00:16-00:00:20"]))

전보다는 개선되었지만 이 역시 시간초과... 현재 시점의 시청자수를 구하는걸 미리 배열로 만들어놓지 않고 순회하면서 찾는 것으로 변경해보기로 했다.

성공!

def strToTime(str):
    str = str.split(':')
    return int(str[0]) * 3600 + int(str[1]) * 60 + int(str[2])

def timeToStr(time):
    h = time // 3600
    time = time % 3600
    m = time // 60
    sec = time % 60
    return f'{h:0{2}d}:{m:0{2}d}:{sec:0{2}d}'

def solution(play_time, adv_time, logs):
    play_time = strToTime(play_time)
    adv_time = strToTime(adv_time)
    timeArr = [0] * play_time
    logs = list(map(lambda x: x.split('-'), logs))
    for i in range(len(logs)):
        logs[i][0] = strToTime(logs[i][0])
        logs[i][1] = strToTime(logs[i][1])

    logLen = len(logs)
    logs = sorted(logs, key = lambda x: x[0])
    enter = list(map(lambda x : x[0], logs))
    out = list(map(lambda x: x[1], logs))
    enter.sort()
    out.sort()
    enter_cur = 0
    out_cur = 0
    viewer = 0
    for t in range(len(timeArr)):
        while enter_cur < logLen and t == enter[enter_cur] :
            viewer += 1
            enter_cur+=1

        while out_cur < logLen and t == out[out_cur]:
            viewer -= 1
            out_cur += 1
        timeArr[t] = viewer

	# max값 찾는 변수 maxNum에다가 첫번째 count를 주지 않으면 00:00:00은 고려안함
    # 그래서 테스트 케이스 9,31 만틀리게 됨
    count = sum(timeArr[:adv_time])
    maxNum = count
    answer = 0
    l, r = 0, adv_time
    while r < play_time:
        count = count - timeArr[l] + timeArr[r]
        r += 1
        l += 1
        if count > maxNum:
            maxNum = count
            answer = l
    remainTime = adv_time - (play_time - answer)
    if remainTime > 0 :
        answer -= remainTime
    return timeToStr(answer)

테스트 케이스 9, 31만 틀리시는 분들 참고...