[프로그래머스] 광고 삽입 / KAKAO BLIND RECRUITMENT / 파이썬

문제

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

 문제를 딱 보고 파싱하고 슬라이딩 윈도우로 풀면 되겠다 했는데 logs의 길이가 최대 30만이라서 계속 시간초과가 떴다. 근데 몇시간동안 안풀리고 답답해서 카카오 공식 해설을 보고 풀었다.. 구간합이라는 테크닉을 필요로 했는데 이 부분을 몰라서 문제를 풀지 못했던 것 같다. 뭔가 카카오 문제들은 풀고나면 쉬워보이는데, 풀기전 까지는 진짜 너어어무 어렵다!

풀이

1. 우선 모든  시간,분,초로된 str을 전부 초 단위로 파싱해준다.

2. 가능한 재생시간의 최대 값인 99시간 59분 59초를 초 단위로 배열을 만들어준다. times[360,000]

3. times배열의 각각의 원소에는 해당 초에 재생이 시작된 횟수 - 해당 초에 재생이 종료된 횟수를 넣어준다.

4. times배열을 times[i] = i 시점부터 i+1시점 까지의 구간을 포함하는 재생된 구간의 개수로 재정의한다.

5. times배열을 times[i] = 0초부터 i+1초 까지 누적된 재생시간으로 재정의한다.

6. 이제 최대 누적 재생 구간을 구하기 위해서 구간합 알고리즘을 사용하면 된다. times[i]시점에서 times[i - 광고 재생시간]을 빼주면  times[i- 광고 재생시간]에서 시작해서 광고 재생시간 동안 재생된 누적 시간이다! 따라서 이제 0 ~ play_time까지 돌면서 초단위로 구간별 누적 시간을 비교에서 최대값을 뽑아주면 되는 것이다. 이때 리턴할 값은 광고가 재생될 시간의 시점이기 때문에 answer을 i로 업데이트로 해주면 된다.

예시

 예시 그림을 보면 1~3단계로 배열을 정의했습니다. 1단계부터  풀이의 3번을 가리키고 이후 4, 5 번을 가리킵니다.

따라서 2~5초 구간의 광고 재생 구간 동안 누적 재생 시간을 구하려면 a[4] - a[1] (11초)을 해주면 됩니다. 왜냐하면

0 ~  i초의 재생 구간은 times[i+1]이기 때문입니다!

 

 

구간합을 아직 배우지 않았다면 여기를 참고해 주세요. 알고리즘에 대해 설명을 잘 해주는 블로그입니다.

코드

def get_seconds(time):
    h, m, s = map(int, time.split(":"))
    return h * 3600 + m * 60 + s


def get_h_m_s(seconds):
    return "{:02d}:{:02d}:{:02d}".format(seconds // 3600, (seconds % 3600) // 60, seconds % 60)


def solution(play_time, adv_time, logs):
    play_time, adv_time = get_seconds(play_time), get_seconds(adv_time)
    max_time = 0
    times = [0] * 360000
    answer = 0

    for log in logs:
        start, end = list(get_seconds(x) for x in log.split("-"))
        times[start] += 1
        times[end] -= 1

    for i in range(1, play_time+1):
        times[i] += times[i-1]

    for i in range(1, play_time+1):
        times[i] += times[i-1]

    for i in range(play_time):
        if i < adv_time - 1:
            if max_time < times[i]:
                max_time = times[i]
                answer = 0
        else:
            if max_time < times[i] - times[i - adv_time]:
                max_time = times[i] - times[i - adv_time]
                answer = i - adv_time + 1

    return get_h_m_s(answer)