[프로그래머스] 2021 카카오 블라인드 - 광고 삽입 파이썬

문제

https://programmers.co.kr/learn/courses/30/lessons/72414

코딩테스트 연습 - 광고 삽입

 

---

풀이

https://tech.kakao.com/2021/01/25/2021-kakao-recruitment-round-1/

2021 카카오 신입공채 1차 온라인 코딩 테스트 for Tech developers 문제해설

 

시작/끝점에서만 그곳을 기준으로 누적합을 따로 계산하려고 굉장히 복잡하게 짜다가 포기했다...

시작 ~ 시작+광고길이

끝 - 광고길이 ~ 끝 

이렇게 점을 만날 때마다 계산하려 했는데 너무 복잡했다 ㅜ

 

결국 해설을 봤는데 완전탐색문제였다.

물론 모든 시간대에서 누적시간을 구하는 O(N*M)이 아니라 전체 시간대에서 재생중인 인원을 저장해놓고 한 번 더 훑으며 최대 누적값을 구하는 O(N)인 듯 하다.

나는 완전탐색은 효율성 테스트를 통과하지 못할 것이라고 생각하고 깊게 생각하지 않았는데

O(N)풀이정도면 시도 해 볼 만 한 풀이였던 것 같다...

여러 방식으로 생각해봐야겠다.

 

해설에 포함된 풀이와 내 코드이다.

 

---

문제 풀이

문제를 쉽게 해결하려면, 등장하는 모든 시각을 초로 환산하여 접근하는 것이 필요합니다. play_time이 99시 59분 59초이하가 되므로, 문제에서 나올 수 있는 모든 시각의 개수는 100 * 60 * 60 = 360000개를 넘지 않습니다.

STEP 1.

매개변수로 주어진 play_time, adv_time, logs에 대해서, 시각을 초로 환산하여 아래와 같이 저장합니다.

logs_start_sec[i] = logs[i]의 시작 시각을 초로 환산한 값

logs_end_sec[i] = logs[i]의 종료 시각을 초로 환산한 값

play_time_sec = play_time을 초로 환산한 값

adv_time_sec = adv_time을 초로 환산한 값

STEP 2.

다음과 같이 total_time 배열을 정의합니다.

total_time[x] = x 시각에 시작된 재생 구간의 개수 – x 시각에 종료된 재생구간의 개수

이렇게 정의한 total_time 배열은 STEP 1.에서 만든 logs_start_sec과 logs_end_sec 배열을 사용하여 구해줄 수 있습니다.

for i = 0 ~ logs의 마지막 인덱스
    total_time[logs_start_sec[i]] = total_time[logs_start_sec[i]] + 1
    total_time[logs_end_sec[i]] = total_time[logs_end_sec[i]] - 1

STEP 3.

다음과 같이 total_time 배열을 재정의합니다.

total_time[x] = 시각 x부터 x+1까지 1초 간의 구간을 포함하는 재생 구간의 개수

재정의된 total_time 배열은 STEP 2.에서 만든 기존의 total_time 배열을 이용하여 계산할 수 있습니다.

for i = 1 ~ (play_time_sec - 1)
    total_time[i] = total_time[i] + total_time[i - 1]

STEP 4.

다음과 같이 total_time 배열을 재정의합니다.

total_time[x] = 시각 0부터 x+1까지 x+1초 간의 구간을 포함하는 누적 재생시간

재정의된 total_time 배열은 STEP 3.에서 만든 기존의 total_time 배열을 이용하고, 완전히 똑같은 반복문을 한 번 더 실행하면 구해줄 수 있습니다.

for i = 1 ~ (play_time_sec - 1)
    total_time[i] = total_time[i] + total_time[i - 1]

STEP 5.

마지막으로 정답을 구하는 과정입니다.

for i = (adv_time_sec - 1) ~ (play_time_sec - 1)
    if ( i >= at) 
        max_time = max(max_time, total_time[i] - total_time[i - at] )
    else 
        max_time = max(max_time, total_time[i])

위 코드는 반복문을 돌며 시각 i - at + 1에 광고를 넣을 때의 누적 재생 시간을 구하여, 그중에서 가장 긴 시간을 max_time에 넣어주고 있습니다. max_time 값이 마지막으로 업데이트될 때의 시각 i - at + 1을 HH:MM:SS 형태로 변환한 값이 문제에서 요구하는 정답입니다.

 

def solution(play_time, adv_time, logs):
    #step1 초 단위로 바꾸기
    pt = int(play_time[:2])*3600+int(play_time[3:5])*60+int(play_time[6:8])
    at = int(adv_time[:2])*3600+int(adv_time[3:5])*60+int(adv_time[6:8])
    
    times = []
    for l in logs:
        times.append((int(l[:2])*3600+int(l[3:5])*60+int(l[6:8]), 0))
        times.append((int(l[-8:-6])*3600+int(l[-5:-3])*60+int(l[-2:]), 1))
    times.sort()
    
    #step2
    cumltime = [0]*(pt+1)
    for t in times:
        if t[1] == 0: #start
            cumltime[t[0]] += 1
        else:
            cumltime[t[0]] -= 1
    
    #step3 초별 재생인원 누적해서 구하기
    for i in range(1, pt+1):
        cumltime[i] += cumltime[i-1]
    
    #step4, 5
    cumlplayt = sum(cumltime[:at+1])
    maxplayt = cumlplayt
    answer = 0
    for i in range(pt-at+1):
        cumlplayt -= cumltime[i]
        cumlplayt += cumltime[i+at]
        if cumlplayt > maxplayt:
            maxplayt = cumlplayt
            answer = i+1
    
    return format(answer//3600, '02')+":"+format((answer%3600)//60, '02')+":"+format(answer%60, '02')

 

해설에서는 step4에서 누적값을 반복문을 한 번 더 돌려서 미리 구해놓은 것 같은데

나는 누적하면서 정답을 같이 구했다.