[프로그래머스] 광고 삽입 파이썬

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/72414?language=python3 

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

 

역시 카카오 시간관련 문제를 좋아한다.

다행인건 시간이 복잡하지 않다는 것이다.

 

이 문제는 전체 구간의 길이가 주어졌을 때 특정 구간의 합이 가장 큰것의 시작점을 찾는 것이다.

근데 이때 그 구간이 여러개라면 가장 먼저 나온 구간의 시작점을 구하는 문제이다.

 

먼저 구간의 길이를 구하자

문제로 주어진 play time은 최대 99시간59분59초이다.

이를 초로 환산하면 100*60*60 = 360,000 이므로 생각보다 많지 않기 때문에 모든 시간을 초로 변환해서 사용하자.

그래서 주어지는 play time을 초로 바꿔서 그 길이+1만큼 구간을 할당 해줬다.

 

다음 logs로 주어지는 구간들을 표시해줘야한다.

첫번째는 시작시각 두번째는 종료시각이다.

그래서 배열[시작시각] += 1, 배열[종료시각] -=1 을 저장해서 누적합에 사용하자.

 

전체 구간이 10초이고, 00:00:01-00:00:03, 00:00:01:00:00:04 이라면

배열은 아래와 같다

0 2 0 -1 -1 0 0 0 0 0

 

다음은 누적합을 구해야한다.

현재 배열에는 해당 시점에 들어오고 나간것이 기록되어 있기 때문에 

이는 1~play_time까지 현재 시점과 이전 시점의 값을 더해주면 된다.

배열[현재] += 배열[이전] 이 된다.

 

위에서 구한 배열을 사용한다면 아래와 같다.

0 2 2 1 0 0 0 0 0 0

 

마지막으로 구간합은 투 포인터를 사용했다.

시작과 끝을 한칸씩 옮기면서 구간합을 구하고 최대값인 시점의 시작점을 기록했다.

 

def solution(play_time, adv_time, logs):
    global sec_arr, play_time_sec, adv_time_sec

    play_time_sec = convert_time_to_sec(play_time.split(':')) + 1
    adv_time_sec = convert_time_to_sec(adv_time.split(':'))

    sec_arr = [0] * (play_time_sec)
    set_sec_arr(logs)
    return search_start_time()

def search_start_time():
    start = 0
    ans_cnt = cnt = sum(sec_arr[:adv_time_sec])
    ans_str = 0
    for end in range(adv_time_sec, play_time_sec):
        cnt -= sec_arr[start]
        start += 1
        cnt += sec_arr[end]

        if ans_cnt < cnt:
            ans_cnt = cnt
            ans_str = start
    return convert_sec_to_time(ans_str)
def set_sec_arr(logs):
    global sec_arr
    for log in logs:
        start = convert_time_to_sec(log[:8].split(':'))
        end = convert_time_to_sec(log[9:].split(':'))
        sec_arr[start] += 1
        sec_arr[end] -= 1

    for idx in range(1, play_time_sec):
        sec_arr[idx] += sec_arr[idx - 1]

def convert_time_to_sec(t):
    h = 60 * 60 * int(t[0])
    m = 60 * int(t[1])
    c = int(t[2])

    return h + m + c
def convert_sec_to_time(sec):
    h = sec // (60 * 60)
    sec %= (60 * 60)
    m = sec // 60
    sec %= 60
    s = sec
    return '%02d:%02d:%02d' % (h, m, s)