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

문제링크

문제 설명

카카오TV에서 유명한 크리에이터로 활동 중인 죠르디는 환경 단체로부터 자신의 가장 인기있는 동영상에 지구온난화의 심각성을 알리기 위한 공익광고를 넣어 달라는 요청을 받았습니다. 평소에 환경 문제에 관심을 가지고 있던 “죠르디”는 요청을 받아들였고 광고효과를 높이기 위해 시청자들이 가장 많이 보는 구간에 공익광고를 넣으려고 합니다. “죠르디”는 시청자들이 해당 동영상의 어떤 구간을 재생했는 지 알 수 있는 재생구간 기록을 구했고, 해당 기록을 바탕으로 공익광고가 삽입될 최적의 위치를 고를 수 있었습니다. 참고로 광고는 재생 중인 동영상의 오른쪽 아래에서 원래 영상과 동시에 재생되는 PIP(Picture in Picture) 형태로 제공됩니다.

다음은 “죠르디”가 공익광고가 삽입될 최적의 위치를 고르는 과정을 그림으로 설명한 것입니다.

• 그림의 파란색 선은 광고를 검토 중인 “죠르디” 동영상의 전체 재생 구간을 나타냅니다.

  • 위 그림에서, “죠르디” 동영상의 총 재생시간은 02시간 03분 55초 입니다.

• 그림의 검은색 선들은 각 시청자들이 “죠르디”의 동영상을 재생한 구간의 위치를 표시하고 있습니다.

  • 검은색 선의 가운데 숫자는 각 재생 기록을 구분하는 ID를 나타냅니다.
  • 검은색 선에 표기된 왼쪽 끝 숫자와 오른쪽 끝 숫자는 시청자들이 재생한 동영상 구간의 시작 시각과 종료 시각을 나타냅니다.
  • 위 그림에서, 3번 재생 기록은 00시 25분 50초 부터 00시 48분 29초 까지 총 00시간 22분 39초 동안 죠르디의 동영상을 재생했습니다. 1
  • 위 그림에서, 1번 재생 기록은 01시 20분 15초 부터 01시 45분 14초 까지 총 00시간 24분 59초 동안 죠르디의 동영상을 재생했습니다.

• 그림의 빨간색 선은 “죠르디”가 선택한 최적의 공익광고 위치를 나타냅니다.

  • 만약 공익광고의 재생시간이 00시간 14분 15초라면, 위의 그림처럼 01시 30분 59초 부터 01시 45분 14초 까지 공익광고를 삽입하는 것이 가장 좋습니다. 이 구간을 시청한 시청자들의 누적 재생시간이 가장 크기 때문입니다.

  • 01시 30분 59초
    

    부터

    01시 45분 14초
    

    까지의 누적 재생시간은 다음과 같이 계산됩니다.

    • 01시 30분 59초 부터 01시 37분 44초 까지 : 4번, 1번 재생 기록이 두차례 있으므로 재생시간의 합은 00시간 06분 45초 X 2 = 00시간 13분 30초
    • 01시 37분 44초 부터 01시 45분 14초 까지 : 4번, 1번, 5번 재생 기록이 세차례 있으므로 재생시간의 합은 00시간 07분 30초 X 3 = 00시간 22분 30초
    • 따라서, 이 구간 시청자들의 누적 재생시간은 00시간 13분 30초 + 00시간 22분 30초 = 00시간 36분 00초입니다.

[문제]

“죠르디”의 동영상 재생시간 길이 play_time, 공익광고의 재생시간 길이 adv_time, 시청자들이 해당 동영상을 재생했던 구간 정보 logs가 매개변수로 주어질 때, 시청자들의 누적 재생시간이 가장 많이 나오는 곳에 공익광고를 삽입하려고 합니다. 이때, 공익광고가 들어갈 시작 시각을 구해서 return 하도록 solution 함수를 완성해주세요. 만약, 시청자들의 누적 재생시간이 가장 많은 곳이 여러 곳이라면, 그 중에서 가장 빠른 시작 시각을 return 하도록 합니다.

[제한사항]

• play_time, adv_time은 길이 8로 고정된 문자열입니다.

  • play_time, adv_time은 HH:MM:SS 형식이며, 00:00:01 이상 99:59:59 이하입니다.
  • 즉, 동영상 재생시간과 공익광고 재생시간은 00시간 00분 01초 이상 99시간 59분 59초 이하입니다.
  • 공익광고 재생시간은 동영상 재생시간보다 짧거나 같게 주어집니다.

• logs는 크기가 1 이상 300,000 이하인 문자열 배열입니다.

  • logs 배열의 각 원소는 시청자의 재생 구간을 나타냅니다.

  • logs 배열의 각 원소는 길이가 17로 고정된 문자열입니다.

  • logs 배열의 각 원소는

    H1:M1:S1-H2:M2:S2
    

    형식입니다.

    • H1:M1:S1은 동영상이 시작된 시각, H2:M2:S2는 동영상이 종료된 시각을 나타냅니다.
    • H1:M1:S1는 H2:M2:S2보다 1초 이상 이전 시각으로 주어집니다.
    • H1:M1:S1와 H2:M2:S2는 play_time 이내의 시각입니다.

• 시간을 나타내는 HH, H1, H2의 범위는 00~99, 분을 나타내는 MM, M1, M2의 범위는 00~59, 초를 나타내는 SS, S1, S2의 범위는 00~59까지 사용됩니다. 잘못된 시각은 입력으로 주어지지 않습니다. (예: 04:60:24, 11:12:78, 123:12:45 등)

• return 값의 형식

  • 공익광고를 삽입할 시각을 HH:MM:SS 형식의 8자리 문자열로 반환합니다.

[입출력 예]

입출력 예에 대한 설명

입출력 예 #1 문제 예시와 같습니다.

입출력 예 #2

01:00:00에 공익광고를 삽입하면 26:00:00까지 재생되며, 이곳이 가장 좋은 위치입니다. 이 구간의 시청자 누적 재생시간은 다음과 같습니다.

• 01:00:00-11:00:00 : 해당 구간이 1회(2번 기록) 재생되었으므로 누적 재생시간은 10시간 00분 00초 입니다.
• 11:00:00-21:00:00 : 해당 구간이 2회(2번, 4번 기록) 재생되었으므로 누적 재생시간은 20시간 00분 00초 입니다.
• 21:00:00-26:00:00 : 해당 구간이 1회(4번 기록) 재생되었으므로 누적 재생시간은 05시간 00분 00초 입니다.
• 따라서, 이 구간의 시청자 누적 재생시간은 10시간 00분 00초 + 20시간 00분 00초 + 05시간 00분 00초 = 35시간 00분 00초 입니다.
• 초록색으로 표시된 구간(69:59:59-94:59:59)에 광고를 삽입해도 동일한 결과를 얻을 수 있으나, 01:00:00이 69:59:59 보다 빠른 시각이므로, "01:00:00"을 return 합니다.

입출력 예 #3

동영상 재생시간과 공익광고 재생시간이 같으므로, 삽입할 수 있는 위치는 맨 처음(00:00:00)이 유일합니다.

주절주절

2021 카카오 블라인드 채용에 나온 문제라 반가운 마음이 들었습니다.

저 역시 카카오 입사했던 19년도에 2번의 코딩테스트와 인터뷰에선 라이브 알고리즘 테스트를 보았던 기억이 납니다 : )

그 당시엔 코딩테스트를 준비하는데 참 많은 시간을 들여 간절히 준비했던 것 같습니다.

이렇게 취미(?)로 알고리즘 문제풀이를 하려고 오랜만에 보니, ‘그 당시의 내가 이런 문제들을 3-40분에 하나씩 풀어 재꼈다고?’ 하는 생각이 들었습니다.

프로그래머스 사이트도 지금과 같은 많은 연습문제들이 있진 않았던 것 같습니다.

(취준생이었던 제가 닥치는데로 문제를 풀어서… 프로그래머스 순위 3위까지 찍던 시절이죠ㅎㅎㅎ)

조만간 기회가 되면 제 개인적인 SW개발직무 코딩테스트 준비과정도 정리해 보겠습니다.

Sol

문제의 이미지를 보며, 옛날에 풀었던 문제 하나가 떠올랐습니다. 이 문제를 풀어보신 분은 나중에 아래 문제도 풀어보시길 추천합니다!

• 디스크 컨트롤러

  
  

문제를 접근하는 아이디어를 떠올리면 쉽게 풀리는 문제였던 것 같습니다.

1. 먼저 입력 받은 시간 데이터들을 ‘초’ 기준으로 변환해 주었습니다.
2. 전체 시간만큼의 0으로 채워진 리스트(n_count)를 하나 선언합니다.
3. log별로 시작지점과 끝 지점에 +1과 -1을 넣어 주었습니다.

아래 이미지와 같은 상황에선, log들의 시작과 끝에 맞춰 n_count가 생성되었을 것 입니다.

1. 이제 이 n_count를 활용해 ‘특정 시각 기준 시청자 수’를 구할 수 있습니다.

   1번 인덱스부터, n_count[idx] = n_count[idx] + n_count[idx-1], 즉 누적을 해주면 됩니다.

   위 그림의 n_count(실시간) 예시를 보면 이해가 더 쉬울 것 입니다. 특정 시간에 몇명이 보고 있는지가 초점입니다!

2. 4번과 마찬가지로 이번엔 동일한 방법을 한번 더 적용하면 어떻게 될까요?

   -> n_count를 활용해 ‘특성 시각 기준 “누적” 시청자 수’를 구할 수 있습니다.

   역시 위 그림의 n_count(누적)이 어떻게 생기는지를 보시면 이해가 쉬울 것 입니다!

   (저는 이 문제를 풀며 마치 고등학교 수학에서 배웠던 미분 적분의 관계랑도 비슷한 느낌을 받았네요. 미분을통해 순간속도를 얻고 또 미분하면 가속도를 얻고, 역으로는 적분으로 얻을 수 있었던…. 네, 이 문제와 관련없는 뻘소립니다.)

   
   

3. 자, 그럼 5번까지 과정으로 누적시청자를 왜 구했는가? 는 바로 특정 구간 내 시청자 수를 구하기 위해서 입니다.

   위 그림에서와 같이 7초부터 12초 구간 내 시청자 수를 구하고 싶다면, 간단하게 n_count[12] - n_count[7] 로 구할 수 있습니다. 이제 이를 활용하면 누적 재생수가 가장 많은 구간을 찾고 싶은 죠르디를 간단히 도와줄 수 있겠죠?

4. 마지막에 output 포맷을 맞춰주는데는 divmod()를 활용했습니다.

코드는 아래와 같습니다.

Code

def solution(play_time, adv_time, logs):
    answer = 0
    # 입력 받은 시간 데이터들 sec 기준으로 변환
    playtime, advtime = play_time.split(":"), adv_time.split(":")
    playtime = int(playtime[0]) * 3600 + int(playtime[1]) * 60 + int(playtime[2])
    advtime = int(advtime[0]) * 3600 + int(advtime[1]) * 60 + int(advtime[2])

    n_count = [0] * (playtime + 1)

    for log in logs:
        lse = log.split("-")
        ls, le = lse[0].split(":"), lse[1].split(":")
        ls, le = int(ls[0]) * 3600 + int(ls[1]) * 60 + int(ls[2]), int(le[0]) * 3600 + int(le[1]) * 60 + int(le[2])

        n_count[ls] += 1
        n_count[le] -= 1

    # 특정 시간 기준 시청자 수
    for _ in range(1, len(n_count)):
        n_count[_] += n_count[_ - 1]

    # 특정 시간 기준 누적
    for _ in range(1, len(n_count)):
        n_count[_] += n_count[_ - 1]

    max_time = 0
    for start in range(-1, playtime - advtime):
        time = n_count[start + advtime] - n_count[max(start, 0)]

        if time > max_time:
            max_time = time
            answer = start + 1

    m, s = divmod(answer, 60)
    h, m = divmod(m, 60)
    h = '0' + str(h) if h < 10 else str(h)
    m = '0' + str(m) if m < 10 else str(m)
    s = '0' + str(s) if s < 10 else str(s)

    answer = h + ':' + m + ':' + s

    return answer

• 2021 19