광고삽입

누적합을 써야하는 문제인것같았다.
시간 길이가 int형보다 작기때문에 배열이 가능하고
들어가는 누적합은 long형태여야한다 (최악의 경우 logs의 크기와 시간이 합쳐진 값이 int형의 범위를 넘어서므로)

이후 누적합의 값을 하나씩 움직여 이후값이 이전값보다 크다면 answer의 값을 이동시키면 된다.

코드

class Solution {
    public String solution(String play_time, String adv_time, String[] logs) {
        int playTime= timeToInt(play_time);
        int advTime = timeToInt(adv_time);
        long[] time = new long[playTime+1];
        int answer = 0;
        long maxTime = 0;
        for(String log: logs){
            String[] times = log.split("-");
            int start= timeToInt(times[0]);
            int end= timeToInt(times[1]);
            time[start]++;
            time[end]--;
        }
        for(int i=0;i<playTime;i++){
            time[i+1]+=time[i];
            maxTime+=time[i];
        }
     
        long  current = maxTime;
        for(int i=advTime;i<playTime;i++){
            current+= time[i] -time[i-advTime];
            if(current>maxTime){
                maxTime = current;
                answer= i-advTime+1;
            }
        }      
        return String.format("%02d:%02d:%02d",answer/3600,answer%3600/60,answer%60);
    }
    int timeToInt(String time){
        String[] times = time.split(":");
        int intTime =Integer.parseInt(times[0])*60*60+Integer.parseInt(times[1])*60+Integer.parseInt(times[2]);
        return intTime;
    }
}

맨 처음 문제를 풀었을때는 start와 end 값을 이중포문을 통해서 누적시켰으나 생각해보니 누적합을 시킬때 한번에 하는 방법이 있었다는것을 잊고있었다.