누적합과 그 응용문제이다

누적합

배열 A의 원소 a[0], a[1], ..., a[n-1]에 대하여, a[i]...a[j]의 원소의 합을 여러번 구해야 하는 경우가 있다. A가 변하지 않는다면 쿼리가 들어올 때마다 배열의 합을 구하는 것은 비효율적이다.
${\rm S[x]}=\sum\limits_{i=0}^{x}{a_i}$ 이라 할 때
$\sum\limits_{i=x}^ya_i=\rm{S[y]-S[x]}$ 이므로 $O(1)$만에 계산할 수 있다.

누적합 응용

배열 A의 원소 a[0], a[1], ..., a[n-1]에 대하여, a[i]...a[j]의 원소에 덧셈/뺄셈을 q번 반복한다고 하자. 그냥 짜면 위에서와 같이 $O(nq)$가 된다.
하지만 누적합을 이용하면 $O(q+n)$만에 해결할 수 있다.
(물론 1차원 배열의 경우, 세그먼트 트리를 이용하면 $O(log(n))$만에도 가능하다)

예시 문제

A = [0, 0, 0, 0, 0, 0, 0]이고
$q_1$ - a[2]~a[5]에 +3
$q_2$ - a[0]~a[3]에 -2
$q_3$ - a[2]~a[6]에 +1

예시 풀이

새로운 배열 B[0...n+1]을 0으로 초기화한다. (B는 A보다 1 크다)
$q_1$: B[2]에는 +3을, B[6]에는 -3을 한다.
$q_2$: B[0]에는 -2을, B[4]에는 +2을 한다.
$q_3$: B[2]에는 +1을, B[7]에는 -1을 한다.
쿼리가 끝나면 B = [-2, 0, 4, 0, 2, 0, -3, -1]이고, B를 누적합하면
B = [-2, -2, 2, 2, 4, 4, 1, 0]이다
마지막으로 A에 B를 더하면
A = [-2, -2, 2, 2, 4, 4, 1]이 된다.
사실 초기 배열이 0으로 초기화되어 있지 않아도 된다는 것을 알 수 있다.

문제 풀이

제한조건 활용

1. play_time은 최대 99:59:59이므로 초단위로 바꾸면 최대 배열의 길이는 100x60x60=360000이다. 문제에 등장하는 모든 시각을 초단위로 바꾸어 배열에 저장할 수 있다.

   adv_count[x]는 x초에 존재하는 광고의 개수

2. log가 $t_1 - t_2$이면 $t_1 \leq t < t_2$동안 광고가 재생된다고 정의하자.($t_2$는 포함되지 않는것에 주의).

   누적합을 응용하여 adv_count[]를 빠르게 업데이트 할 수 있다.

필요한 함수를 정의

문자열(str)로 표현된 시각을 초(int)로 바꾸는 것과, 정답을 리턴하기 위해 초를 문자열로 바꾸는 함수가 필요해보인다.

def str2int(time):
'''HH:MM:SS의 문자열을 초 단위로 변환하는 함수'''
    h, m, s = map(int, time.split(':'))
    return s + 60*m + 60*60*h


def int2str(seconds):
'''초 단위 정수를 HH:MM:SS로 변환하는 함수'''
    h = seconds // 3600
    seconds %= 3600
    m = seconds // 60
    s = seconds % 60
    #print(h, m, s)
    return f'{h:02}:{m:02}:{s:02}'

adv_count

시작시간과 끝시간을 s, e라 하면
adv_count[s] += 1, adv_count[e] -= 1을 해준다.
(끝시간은 광고를 포함하지 않는다)

앞의 예시처럼 두개의 배열을 만드지 않고 adv_count을 재활용하여 누적합을 구하면
adv_count[x]는 x초에 존재하는 광고의 개수가 된다.

PLAY_SIZE = str2int(play_time)
ADV_SIZE = str2int(adv_time)

adv_count = [0 for _ in range(PLAY_SIZE + 1)]
    
for log in logs:
	start_time, end_time = log.split('-')
	start_time = str2int(start_time)
	end_time = str2int(end_time)
	adv_count[start_time] += 1
	adv_count[end_time] -= 1
    
# complete adv_count
for i in range(PLAY_SIZE - 1):
    adv_count[i + 1] += adv_count[i]

count_sum

count_sum[x] 0초부터 x초까지 누적재생시간

count_sum = [0 for _ in range(PLAY_SIZE + 1)]
count_sum[0] = adv_count[0]
for i in range(1, len(count_sum)):
	count_sum[i] = adv_count[i] + count_sum[i - 1]

최대 누적재생시간의 시작점 찾기

cur_count = count_sum[ADV_SIZE - 1]
max_idx = 0
max_count = cur_count
for i in range(1, PLAY_SIZE - ADV_SIZE + 2):
    cur_count = count_sum[i + ADV_SIZE - 1] - count_sum[i - 1]

    if cur_count > max_count:
        max_count = cur_count
        max_idx = i

# max_idx는 최대 누적재생시간의 시작점(초)이므로, 다시 문자열로 바꾼다
answer = int2str(max_idx)

최종 코드

최종 시간복잡도는 선형시간이다.

def str2int(time):
    h, m, s = map(int, time.split(':'))
    return s + 60*m + 60*60*h

def int2str(seconds):
    h = seconds // 3600
    seconds %= 3600
    m = seconds // 60
    s = seconds % 60
    return f'{h:02}:{m:02}:{s:02}'

def solution(play_time, adv_time, logs):
    answer = ''
    PLAY_SIZE = str2int(play_time)
    ADV_SIZE = str2int(adv_time)
    
    adv_count = [0 for _ in range(PLAY_SIZE + 1)]
    
    for log in logs:
        start_time, end_time = log.split('-')
        start_time = str2int(start_time)
        end_time = str2int(end_time)
        
        adv_count[start_time] += 1
        adv_count[end_time] -= 1
    

    for i in range(PLAY_SIZE - 1):
        adv_count[i + 1] += adv_count[i]
    
    count_sum = [0 for _ in range(PLAY_SIZE + 1)]
    count_sum[0] = adv_count[0]
    for i in range(1, len(count_sum)):
        count_sum[i] = adv_count[i] + count_sum[i - 1]
    

    cur_count = count_sum[ADV_SIZE - 1]
    max_idx = 0
    max_count = cur_count
    for i in range(1, PLAY_SIZE - ADV_SIZE + 2):
        cur_count = count_sum[i + ADV_SIZE - 1] - count_sum[i - 1]
        
        if cur_count > max_count:
            max_count = cur_count
            max_idx = i

    answer = int2str(max_idx)
    return answer