광고 삽입

문제 설명

카카오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자리 문자열로 반환합니다.

---

전체 코드

def convert_seconds(time):
    string=time.split(':')
    hour,minute,second=string
    hour=hour.lstrip('0')
    if hour=='':
        hour='0'
        
    hour=int(hour)
    
    minute=minute.lstrip('0')
    if minute=='':
        minute='0'
    
    minute=int(minute)
    
    second=int(second)
    
    return hour*3600+minute*60+second
    
def convert_log(log):
    start,end=log.split('-')
    start_seconds=convert_seconds(start)
    end_seconds=convert_seconds(end)
    
    return (start_seconds,end_seconds)

def convert_time(second):
    hour=second//3600
    hour_s=str(hour).zfill(2)
    second-=(hour*3600)
    
    
    minute=second//60
    minute_s=str(minute).zfill(2)
    second-=(minute*60)
    
    return hour_s+":"+minute_s+":"+str(second).zfill(2)
    
    
def solution(play_time, adv_time, logs):
    answer = ''
    
    play_seconds=convert_seconds(play_time)
    
    play_adv=convert_seconds(adv_time)
    
    #최대 100*60*60의 1초짜리 배열
    #최대 36만개이므로 O(N)으로 풀면 그렇게 크지 않은 N이다.
    # 0~ play_seconds까지 체크
    seconds=[0]*(play_seconds+1)

    #O(n)
    for log in logs:
        #로그 초 단위로 변환하기
        play_log=convert_log(log)
        
        #시작 구간에 +1, [끝 구간]에 -1 처리
        #시작 구간에는 시청자 1명이 더 들어온 것과 같으며
        #끝 구간에는 시청자 1명이 나간 것과 같다.
        start,end=play_log
        seconds[start]+=1
        seconds[end]-=1
    
    #구간 별 시청자수를 기록한다.
    #dp[i]=dp[i]+dp[i-1] , O(N)
    for i in range(1,len(seconds)):
        seconds[i]=seconds[i]+seconds[i-1]
    
    #모든 구간의 누적 재생 시간을 기록한다.
    #dp[i]=dp[i]+dp[i-1], O(N)
    for i in range(1,len(seconds)):
        seconds[i]=seconds[i]+seconds[i-1]
    
    #adv_time만큼의 구간 내의 누적 시청 기록들 계산 및 최대 누적 시청 기록 갱신
    
    #최대 누적 시청 기록을 갖는 시작점
    max_time_start=0
    #최대 누적 시청 기록
    most_view=0
    for i in range(play_adv-1,len(seconds)):
        #i가 play_adv보다 크거나 같으면, play_adv 크기만큼의 구간의 누적 시청 기록 계산 가능.
        if i>=play_adv:
            #더 큰 누적 시청기록으로 갱신할 수 있으면,누적 시청 기록과 시작 지점을 갱신한다.
            if most_view<seconds[i]-seconds[i-play_adv]:
                most_view=seconds[i]-seconds[i-play_adv]
                max_time_start=i+1-play_adv
                
        #i가 play_adv-1이면 0~play_adv-1까지의 구간을 뜻한다. (단 1개의 구간)
        else:
            most_view=max(most_view,seconds[i])
            max_time_start=0
    
    answer=convert_time(max_time_start)
    
    return answer

---

해설

1.시간 문자열 → 초 단위로 변환하는 함수 구현

시간 문자열을 ':"을 기준으로 나누면 시,분,초로 나눠진다.
그리고 시와 분은 앞에 '0'이 있을 수 있으므로 lstrip('0')을 이용해 왼쪽에 있는 '0'을 모조리 지운다.
이 때, '00'과 같은 경우는 전부 지워져 ''이 될 수 있으므로 '0'으로 예외처리 해준다.

그리고 이 시,분,초를 int()로 정수화 시킨 다음, 시3600+분60+초로 만들어서 초 단위의 시간을 리턴해준다.

def convert_seconds(time):
    string=time.split(':')
    hour,minute,second=string
    hour=hour.lstrip('0')
    if hour=='':
        hour='0'
        
    hour=int(hour)
    
    minute=minute.lstrip('0')
    if minute=='':
        minute='0'
    
    minute=int(minute)
    
    second=int(second)
    
    return hour*3600+minute*60+second

2.초 단위 →시간 문자열로 변환하는 함수 구현

초 단위의 시간에서 //3600을 하면 시간을 구할 수 있다.
이 시간 정수를 str()을 이용해 문자열로 만든 후 zfill(2)를 사용하여 2자리가 되도록 왼쪽에 '0'을 넣는다.
예를 들면 '1'의 경우 '01'이 되고, '10'의 경우는 이미 2자리이므로 적용되지 않는다.

초 단위 시간에서 시간*3600을 뺴면 분과 초만 남는다.

여기서 //60을 하면 분을 얻어낼 수 있고, 이를 시를 처리했던 것처럼 처리한다.

이 초단위 시간에서 분*60을 빼면 초만 남는다.

이 방식을 이용해 "시간:분:"초의 포맷의 문자열을 얻어낼 수 있다.

def convert_time(second):
    hour=second//3600
    hour_s=str(hour).zfill(2)
    second-=(hour*3600)
    
    
    minute=second//60
    minute_s=str(minute).zfill(2)
    second-=(minute*60)
    
    return hour_s+":"+minute_s+":"+str(second).zfill(2)
    

3.초 단위의 시간 배열 만들기

이 문제는 00:00:00 부터 99:59:59까지의 시간 구간을 갖고 있다.
이를 초 단위로 변경하면 0부터359999까지의 범위를 갖는 배열로 볼 수 있다.
O(n)으로 풀면 최대 36만개 뿐이므로 그리 크지 않은 n이다.

   #최대 100*60*60의 1초짜리 배열
    #최대 36만개이므로 O(N)으로 풀면 그렇게 크지 않은 N이다.
    # 0~ play_seconds까지 체크
    seconds=[0]*(play_seconds+1)

4.시작 지점에 +1, 끝 지점에 -1을 해준다.

위 그림은 0초부터 20초 이전까지의 상태를 보여주고 있다.

여기서 각 구간의 시작 지점은 시청자 1명이 새로 들어온 것과 같으며, 끝 지점은 시청자 1명이 나간 것과 같다.
이를 그림으로 표현하면 다음과 같다.

위 그림에서 0을 00:00이라고 하자. 00:00 ~ 00:06은 6초로서, [0,1,2,3,4,5]로 나타낼 수 있다.

이를 초 단위 (시작 지점, 끝 지점) 튜플로 나타내면 (0,6)이다. 즉 초[0]에는 +1을 해주고 초[6]에는 -1을 해준다. 시간 복잡도는 O(N)이다.

    #O(n)
    for log in logs:
        #로그 초 단위로 변환하기
        play_log=convert_log(log)
        
        #시작 지점에 +1, [끝 지점]에 -1 처리
        #시작 지점에는 시청자 1명이 더 들어온 것과 같으며
        #끝 지점에는 시청자 1명이 나간 것과 같다.
        start,end=play_log
        seconds[start]+=1
        seconds[end]-=1

5. DP를 이용해 구간 별 시청자수를 기록한다. (O(N))

4.에서 기록한 상태를 이용해 dp[i]=dp[i]+dp[i-1] 점화식을 적용한다.
이렇게 하면 각 초에서 현재 시청자 수가 몇명인지 알수가 있다.
예를 들어, 12초의 상태에서는 시청자가 3명있고, 7초에서는 시청자가 0명임을 알 수 있다.

    #구간 별 시청자수를 기록한다.
    #dp[i]=dp[i]+dp[i-1] , O(N)
    for i in range(1,len(seconds)):
        seconds[i]=seconds[i]+seconds[i-1]

6. 5.와 똑같은 dp를 이용해 각 구간의 누적 시청 기록을 계산한다. (O(N))

5.의 상태에서 dp[i]=dp[i]+dp[i-1] 점화식을 다시 적용하면, 각 구간의 누적 시청 기록을 얻을 수 있다.
각 구간의 누적 시청 기록을 계산 해놓는 이유는, [구간 X]의 누적 시청 기록 - [구간X-재생길이]의 누적 시청기록을 빼면 정확하게 재생 길이만큼의 누적 시청 기록을 얻을 수 있기 때문이다.

(EX: (a0+a1+a2+...+aX )- (a0+a1+a2+....+a[X-재생길이] )

= a[X-재생길이 +1]+ a[X- 재생길이+2]+....aX )

    #모든 구간의 누적 재생 시간을 기록한다.
    #dp[i]=dp[i]+dp[i-1], O(N)
    for i in range(1,len(seconds)):
        seconds[i]=seconds[i]+seconds[i-1]

7.모든 구간의 누적 재생 시간을 이용하여 재생 길이 구간 내의 누적 시청 기록을 계산한다.

(a0+a1+a2+...+aX )- (a0+a1+a2+....+a[X-재생길이] )= a[X-재생길이 +1]+ a[X- 재생길이+2]+....aX 를이용하여 재생 길이 구간 내의 누적 시청 기록을 구한다.
그림으로 표현하면 다음과 같다.

제일 큰 누적 시청기록을 구해야 하고, 그 중에서도 가장 시작지점이 빠른 것을 찾아야 하므로, 한 번 순회하면서 두 값들을 갱신해준다.

이 모든 과정의 시간 복잡도는 O(N)*4=O(N)이므로 n= 최대 36만이면 충분히 빠르게 해결 가능하다.

#adv_time만큼의 구간 내의 누적 시청 기록들 계산 및 최대 누적 시청 기록 갱신
    
    #최대 누적 시청 기록을 갖는 시작점
    max_time_start=0
    #최대 누적 시청 기록
    most_view=0
    for i in range(play_adv-1,len(seconds)):
        #i가 play_adv보다 크거나 같으면, play_adv 크기만큼의 구간의 누적 시청 기록 계산 가능.
        if i>=play_adv:
            #더 큰 누적 시청기록으로 갱신할 수 있으면,누적 시청 기록과 시작 지점을 갱신한다.
            if most_view<seconds[i]-seconds[i-play_adv]:
                most_view=seconds[i]-seconds[i-play_adv]
                max_time_start=i+1-play_adv
                
        #i가 play_adv-1이면 0~play_adv-1까지의 구간을 뜻한다. (단 1개의 구간)
        else:
            most_view=max(most_view,seconds[i])
            max_time_start=0
    
    answer=convert_time(max_time_start)
    
    return answer