[2021 KAKAO BLIND RECRUITMENT] 광고 삽입

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/72414#fn1

이 문제는 문제의 조건을 어떤 식으로 구현할 것인지를 떠올리면 풀 수 있습니다. 우선 시간:분:초의 형태를 계산하기 편하게 초 단위로 변환합니다. 이후 logs의 시작 시간과 종료 시간을 체크해서 전체 런타임 중 x 시각에 시작된 재생 구간이 존재할 경우 1씩 증가하고 종료된 재생 구간이 존재할 경우 1씩 감소하는 배열을 설정합니다. 그럼 이 배열에는 전체 런타임 중 재생 및 종료의 정보가 기입됩니다.

위에서 만든 배열에서 직전 인덱스의 값과의 합한 배열을 새로 정의합니다. (dp[i] = dp[i]+dp[i-1]) 이 배열은 i 시간부터 i+1까지 시작 및 종료의 정보가 기입됩니다. 여기서 더 확장해서 방금 구한 배열의 직전 인덱서의 값과의 합한 배열을 새로 정의하게 된다면 이 배열은 0부터 1까지, 1부터 2까지 , ... , i부터 i+1까지 구간의 시작 및 종료 정보가 기입됩니다. 즉 0부터 i+1 구간의 누적 재생 시간을 얻게 됩니다.

위에서 구한 누적 재생 시간 배열에서 광고 시간만큼 인덱스의 차를 주어 더해준다면 (dp[i] - dp[i-at]) 광고 시간 동안의 누적 재생 시간을 구할 수 있습니다. 이 값이 최대가 되는 시작 시간을 리턴하여 시간값으로 변환시키면 됩니다. 글에서 작성한 방식은 광고가 끝나는 시간을 기준으로 반복문을 돌렸습니다. 만약 광고의 시작 시간을 기준으로 돌리고 싶으시다면 dp[i+at] - dp[i]로 설정하셔도 됩니다.

다음은 코드입니다.

import java.util.*;

class Solution {
    static int convert(String time){
        String[] arr = time.split(":");
        int hour = Integer.parseInt(arr[0])*60*60;
        int minute = Integer.parseInt(arr[1])*60;
        int second = Integer.parseInt(arr[2]);
        
        return hour + minute + second;
    }
    
    public String solution(String play_time, String adv_time, String[] logs) {
        int pt = convert(play_time);
        int at = convert(adv_time);
        
        // total_time[x] = x 시각에 시작된 재생 구간의 개수 – x 시각에 종료된 재생구간의 개수
        long[] total_time = new long[pt+1];
        for(int i=0;i<logs.length;i++){
            String[] arr = logs[i].split("-");
            total_time[convert(arr[0])]++;
            total_time[convert(arr[1])]--;
        }
        
        // total_time[x] = 시각 x부터 x+1까지 1초 간의 구간을 포함하는 재생 구간의 개수
        for(int i=1;i<=pt;i++) total_time[i] += total_time[i-1];
        
        // total_time[x] = 시각 0부터 x+1까지 x+1초 간의 구간을 포함하는 누적 재생시간
        for(int i=1;i<=pt;i++) total_time[i] += total_time[i-1];
        
        // 0에서 광고가 시작할 경우 total_time[at-1]
        long res = total_time[at-1];
        int idx = 0;
        
        // 광고가 끝나는 시간을 반복문으로 돌려서 최대 누적 재생시간 계산
        for(int i=at;i<=pt;i++){
            // i만큼의 누적 재생시간에서 광고가 시작하기 전인 i-at의 누적 재생시간을 빼면 현재 누적 재생시간 구할 수 있음
            long curr = total_time[i] - total_time[i-at];
            
            // 더 긴 누적 재생 시간이 있을 경우 idx 최신화
            if(res < curr){
                res = curr;
                idx = i-at+1;
            }
        }
        
        // 시간 형식으로 변환
        StringBuilder sb = new StringBuilder();
        int h = idx/3600;
        int m = (idx%3600)/60;
        int s = (idx%3600)%60;
        
        if(h<10) sb.append("0"+h);
        else sb.append(h);
        sb.append(":");
        if(m<10) sb.append("0"+m);
        else sb.append(m);
        sb.append(":");
        if(s<10) sb.append("0"+s);
        else sb.append(s);
        
        return sb.toString();
    }
}