[프로그래머스] 광고 삽입, Python3

문제는 여기!

 

안녕하세요! 이번 포스팅에서는 2021 카카오 블라인드 채용 알고리즘 문제인 "광고 삽입" 문제를 풀이해보겠습니다. 2021년도 레벨3 문제들을 풀어보면서 느낀점은 확실히 예전 년도들에 비해 문제 난이도가 많이 어려웠습니다. 심지어 나온지 얼마 안된 문제여서 풀이를 해주신 분들이 많이 안계셔서 애를 많이 먹기도 했던 문제입니다. 저도 결국 카카오에서 직접 해주신 해설을 봐도 모르겠어서 다른 분의 코드를 참조하면서 이해했습니다. 그럼 풀이 시작할게요!

제한사항 및 유의사항

play_time, adv_time은 길이 8로 고정된 문자열이며, HH:MM:SS 형식입니다. 그리고 00:00:01 ~ 99:59:59 까지의 범위입니다.

광고 재생 시간은 동영상 재생 시간보다 짧거나 같게 주어집니다.

logs는 크기가 1이상 300,000이하 이며, 각 원소는 길이 17로 고정된 문자 입니다. H1:M1:S1-H2:M2:S2 형식이며 -를 기준으로 1은 영상 시작시각, 2는 영상 종료시각을 의미합니다.

각 시각의 형태의 범위는 00 <= HH(H1, H2) <= 99, 00 <= MM(M1, M2) <= 59, 00 <= SS(S1, S2) <= 59 의 범위입니다.

풀이전략

우선, 모든 시간들을 초 단위로 표현했습니다. 처음에는 datetime을 이용하여 풀어야하나? 싶었지만, play_time의 최댓값이 99:59:59이므로 이를 100시간으로 쳐서 초 단위로 표현하면 360,000초 입니다. play_time을 초 단위 만큼 환산하고, 초 단위 크기의 배열을 선언해서 풀이했습니다.

해당 배열의 이름은 accumulate_time으로 선언했고, 만약 play_time이 99:59:59라면

accumulate_time = [0] * (play_time 초로 환산 + 1)로 선언합니다.

아차! 문자열을 초 단위로 환산해주는 메서드, 초 단위를 HH:MM:SS로 표현하기 위한 메서드를 작성해야합니다! 코드를 참조하시면 될 것 같습니다.

이제는 앞에서 선언한 accumulate_time 배열을 이용할 차례입니다. logs들을 반복문으로 돌려가면서 하나의 로그를 "-"로 split하면 시작, 종료 시간이 나옵니다. 이 시작시간과 종료시간을 초로 반환하여 영상이 시작한 시간에는 1, 종료된 시간에는 -1을 넣어줍니다.

accumulate_time[시작시간(초)] = 1

accumulate_time[종료시간(초)] = -1

그 다음 accumulate_time을 1부터 끝까지 반복문을 통해 accumulate_time[i] += accumulate_time[i - 1]을 해줍니다. 이 작업은 i초에 시청한 사람들의 수를 의미합니다. 저는 이 부분부터 이해력이 좋지 않아서 단번에 이해가 되지 않았습니다.

바로 전의 과정인 accumulate_time[i] += accumulate_time[i - 1]을 한번 더 해줍니다. 이 때는 i초에 누적으로 재생중인 영상의 길이를 넣어주는 작업이며, 처음에는 이걸 왜 하는지 몰랐습니다. 아마 제가 문제를 제대로 읽지 않아서 그런거 같은데 accumulate_time[i] += accumulate_time[i - 1]을 왜 두번하는지 그림으로 설명드리겠습니다.

저는 이렇게 상황을 가정했습니다. 그리고 이에 따라서 첫 번째 작업인 각 log들의 재생 시작시간에 1을, 종료시간에 -1을 넣으면 다음 그림과 같이 됩니다.

그 다음, 두 번째 작업인 1초부터 끝까지 i초에 시청자들이 영상을 재생하고 있는 수를 계산하는 작업을 해봅시다.

자 logs에서 1초와 2초에 재생이 시작되고 4초에 재생이 종료된다고 예를 들어 드렸습니다. 그럼 해당 작업을 수행한 결과 play_time이 1초에 시청자들이 영상을 재생하고 있는 수는 1, 2초에는 아까 log에서 2초에 재생이 시작된다고 했으니, 1초에 1명 재생시작, 2초에 1명 재생시작, 총 2명이 2초에 영상을 재생하고 있습니다.

그리고 4초에는 1초에서 시작한 영상, 2초에서 시작한 영상이 모두 종료되었으므로, accumulate_time[4]는 0이 됩니다.

그리고 이 작업을 한번 더 해줍니다.

세 번째 작업을 끝낸 결과입니다. 저는 문제에서 "시청자들의 누적 재생시간이 가장 많이 나오는 곳에 공익광고를 삽입하려고 합니다." 를 읽지 못했습니다.

정신좀 차려 제발

이 세 번째 작업은 해당 i초에 동영상이 재생된 누적 시간을 계산한 결과인데요 좀 더 구체적으로 보겠습니다.

1초에는 영상을 보는 사람이 1명입니다. 그래서 1초에 시청하는 누적 재생 시간은 1이 될 것입니다.

다음 2초입니다. accumulate_time[2]는 3이 나왔으며 이게 무엇을 의미하는 지 보자면,

• 1초에 영상을 시작한 사람은 4초까지 봅니다. 이 사람이 2초까지 영상을 시청하고 있고, 1초 구간부터 영상을 보고 있으니, 2초에는 1 + 1 = 2가 됩니다.
• 다음, 2초에 영상을 시작한 사람이 있습니다. 앞에서 계산한 2에 2초에 영상을 시작한 사람 1을 더해주어 accumulate_time[2] = 3이 되었습니다.

결국 세 번째 작업을 거치고 나서 accumulate_time[i]의 의미는 i초부터 i + 1초 까지 재생되고 있는 영상의 누적 수를 의미합니다. 이와 같은 방식으로 한번 더 3초까지 영상해보죠.

1초에서 영상을 시작한사람, 2초에 영상을 시작한 사람은 모두 4초에 영상을 종료합니다. 3초 구간까지는 모두 시청하고 있기에 accumulate_time[3] += accumulate_time[2] 를 수행하면 5라는 결과가 나옵니다. 이제 마무리로 4초의 상황을 보자면

4초에는 두 사람 모두 영상을 종료해서 accumulate_time[4] += accumulate_time[3] 을 해도 증가되지 않습니다. 이와 같은 방식으로 구간마다 누적 재생시간의 수를 구해줄 수 있습니다. 이제 모든 구간마다 누적 재생시간의 최대인 시간대를 구해야 합니다.

세 번째 작업이 완료된 예시를 갖고 계속 이어보겠습니다. 앞에서 광고 시간은 3초라고 가정을 했습니다. 먼저 최댓값을 저장하기 위한 변수를 선언해보겠습니다.

max_time : 광고를 시작해야 할 시간

max_play : 누적 재생시간의 최대를 저장

그 다음, 반복문을 adv_time - 1부터, play_time까지 돌립니다.

왜 adv_time - 1 부터 반복문을 시작?

제가 이해가 안되었던 부분중에 하나입니다. 광고는 00:00:00초 부터 시작할 수 있기 때문에 반복문의 구간을 00:00:00초에 시작할 경우, 끝나는 시간은 00:00:02초 입니다. 광고가 맨 처음 시작해서 끝나는 구간부터 우리가 체크를 해주어야 합니다.

왜 반복문을 play_time + 1까지 안돌리고 play_time까지만 돌려?

i를 adv_time - 1부터 돌렸습니다. 00:00:00초 부터 광고가 시작되어 00:00:02초에 보여주고 끝나게 되겠죠. 즉 i는 광고를 마지막으로 보여주는 시간이라 생각하시면 될 것 같습니다. 기존의 adv_time이 3으로 예시가 주어져서 adv_time - 1 부터 시작했듯, 반복문의 끝은 play_time + 1( len(accumulate_time) )에서 -1해주어 play_time까지만 돌리면 되겠습니다.

accumulate_time[i] - accumulate_time[i - adv_time]는 i-adv_time+1 초 부터 i초 까지 누적 재생 시간을 구해줍니다. 만약 i가 adv_time보다 작을 경우(맨 처음) 0초부터 광고가 시작되기에, accumulate_time[i] = 0초부터 i초 까지 누적 재생시간이 됩니다. 0초부터 광고가 시작되니깐 accumulate_time[i - adv_time] 구간을 따로 빼서 구해줄 필요가 없기 때문입니다.

accumulate_time[i] - accumulate_time[i - adv_time]의 값을 구해주어 max_play 보다 클 경우 해당 시간에 max_play값을 최댓값으로 저장해주고, max_time은 i - adv_time +1 로 저장해줍니다.

코드는 다음과 같으며, 피드백은 무조건 환영합니다.

def str_to_sec(string):
    hour = int(string[0:2]) * 3600
    minute = int(string[3:5]) * 60
    sec = int(string[6:8])
    return hour + minute + sec


def sec_to_str(second):
    hour = second // 3600
    second %= 3600
    minute = second // 60
    second %= 60
    return str(hour).zfill(2) + ":" + str(minute).zfill(2) + ":" + str(second).zfill(2)


def solution(play_time, adv_time, logs):
    play_time = str_to_sec(play_time)
    adv_time = str_to_sec(adv_time)

    # 누적시간 계산할 배열
    accumulate_time = [0 for _ in range(play_time + 1)]
    for log in logs:
        start, end = log.split("-")
        start = str_to_sec(start)
        end = str_to_sec(end)
        accumulate_time[start] += 1
        accumulate_time[end] -= 1

    # i초에 시청하고 있는 시청자 수
    for i in range(1, play_time + 1):
        accumulate_time[i] += accumulate_time[i - 1]

    # i초의 시청자들의 누적 재생시간
    for i in range(1, play_time + 1):
        accumulate_time[i] += accumulate_time[i - 1]

    max_time = 0
    max_play = 0
    for i in range(adv_time - 1, play_time):
        if i >= adv_time:
            if max_play < accumulate_time[i] - accumulate_time[i - adv_time]:
                max_play = accumulate_time[i] - accumulate_time[i - adv_time]
                max_time = i - adv_time + 1
        else:
            if max_play < accumulate_time[i]:
                max_play = accumulate_time[i]
                max_time = i - adv_time + 1

    return sec_to_str(max_time)