1차원에서 누적합을 나중에 한번에 계산하게 하는 방법을 바로 떠올렸지만,
동영상 시청을 이상, 이하로 접근하여 삽질을 오래 했다.
아래는 이상, 이하로 접근했을 때의 풀이다. 정확도는 80.6점가 나온다.
def time_to_sec(time):
h,m,s = map(int,time.split(":"))
return h*60*60 + m*60 + s
def sec_to_time(sec):
m,s = divmod(sec, 60)
h,m = divmod(m, 60)
return f"{h:02d}:{m:02d}:{s:02d}"
def solution(play_time, adv_time, logs):
play_time_sec = time_to_sec(play_time)
adv_time_sec = time_to_sec(adv_time)
psum = [0]*(play_time_sec+2) # 누적합 한번에 처리하기 위한 리스트
for log in logs:
start, end = map(time_to_sec, log.split("-"))
psum[start] += 1
psum[end+1] -= 1
for i in range(1, play_time_sec+1): # 누적합 계산
psum[i] += psum[i-1]
ans_adv_start_sec = 0
max_sum = float('-inf')
range_psum = [0] * (play_time_sec-adv_time_sec+1) # adv_psum[i]: i초 시각에 초 총합
range_psum[0] = sum(psum[:adv_time_sec])
for i in range(1, len(range_psum)):
range_psum[i] = range_psum[i-1] - psum[i-1] + psum[i+adv_time_sec]
if max_sum < range_psum[i]:
ans_adv_start_sec = i
max_sum = range_psum[i]
return sec_to_time(ans_adv_start_sec)
시청시간을 이상, 이하가 아닌 이상, 미만으로 접근하여 다시 푼 코드는 다음과 같다. 처음에 이상, 이하로 접근하고 우당탕탕 바꾸는 과정이 매우 매끄럽지 못해서 다음에는 예시를 조금 더 잘 들어서 이용하는게 좋을 것 같다.
def time_to_sec(time):
h,m,s = map(int,time.split(":"))
return h*60*60 + m*60 + s
def sec_to_time(sec):
m,s = divmod(sec, 60)
h,m = divmod(m, 60)
return f"{h:02d}:{m:02d}:{s:02d}"
def solution(play_time, adv_time, logs):
play_time_sec = time_to_sec(play_time)
adv_time_sec = time_to_sec(adv_time)
psum = [0]*(play_time_sec+1) # 누적합 한번에 처리하기 위한 리스트
for log in logs:
start, end = map(time_to_sec, log.split("-"))
psum[start] += 1 # 이상
psum[end] -= 1 # 미만
for i in range(1, play_time_sec): # 누적합 계산
psum[i] += psum[i-1]
ans_adv_start_sec = 0
range_psum = [0] * (play_time_sec-adv_time_sec+1) # adv_psum[i]: i초 시각에 초 총합
max_sum = range_psum[0] = sum(psum[:adv_time_sec-1])
for i in range(1, len(range_psum)):
range_psum[i] = range_psum[i-1] - psum[i-1] + psum[i+adv_time_sec-1]
if max_sum < range_psum[i]:
ans_adv_start_sec = i
max_sum = range_psum[i]
return sec_to_time(ans_adv_start_sec)
2022 카카오의 파괴되지 않은 건물은 위 누적합 개념을 2차원에 적용한다. 이러한 유형이 자주 등장하는걸로 보인다.