광고 삽입 (Java)

접근 방법

1. (누적합) Naive하게 i가 0 부터 끝까지 모든 범위의 sum을 구한다면 시간 초과가 날 것은 명백하다. 따라서 logs의 입력을 받을 때, 시청 시작시간과 종료시간만 각각 += 1과 -=1로 마크 해놓은 다음 모든 전처리가 끝나면 마크 해놓은 곳을 0 부터 play_time까지 오른쪽으로 땡겨준다. 그 후엔, 매번 sum을 안구해도 되도록 각 index에 대한 누적합을 미리 계산 해놓는다.
2. (탐색) 우리가 알고 싶은 것은 최대 누적 시간이기 때문에 adv_time만큼의 Sliding Window를 두고 0부터 되는 데까지 이동하면된다. 그 과정에서 특정 구간의 최대 누적 시간은 미리 구해놓은 누적합 배열의 adv_time - i 값에서 i를 뺀 값일 것이다.
3. (구조화) 시간의 String 및 Integer 형변환을 위한 별도의 유틸 메서드를 만들어 놓으면 편하다.

코드

import java.lang.Math;
import java.util.*;

class Solution {
    private int parseTimeToInt(String timeString) {
        String[] hrMinSec = timeString.split(":");
        int ret = 0;
        ret += Integer.parseInt(hrMinSec[0]) * 60 * 60;
        ret += Integer.parseInt(hrMinSec[1]) * 60;
        ret += Integer.parseInt(hrMinSec[2]);
        return ret;
    }
    
    private String intTimeToString(int timeInt) {
        int timeResidue = timeInt;
        String hour = String.valueOf(timeResidue / (60 * 60));
        if (hour.length() < 2) hour = "0" + hour;
        
        timeResidue -= (timeResidue / (60 * 60)) * 60 * 60;
        String min = String.valueOf(timeResidue / 60);
        if (min.length() < 2) min = "0" + min;
        
        timeResidue -= (timeResidue / 60) * 60;
        String sec = String.valueOf(timeResidue);
        if (sec.length() < 2) sec = "0" + sec;
        
        return hour + ":" + min + ":" + sec;
    }
    
    public String solution(String play_time, String adv_time, String[] logs) {
        int play_time_int = parseTimeToInt(play_time);
        int adv_time_int = parseTimeToInt(adv_time);
        
        int[] viewMarks = new int[play_time_int + 1];
        
        for (String log : logs) {
            int startTime = parseTimeToInt(log.substring(0, 8));
            int endTime = parseTimeToInt(log.substring(9));
            viewMarks[startTime] += 1;
            viewMarks[endTime] -= 1;
        }
        
        for (int i = 0; i < play_time_int; i++) {
            viewMarks[i + 1] += viewMarks[i];
        }
        
        int maxAtTime = 0;
        long currCumulative = 0;
        for (int i = 0; i < adv_time_int; i++)
            currCumulative += viewMarks[i];
        
        long maxCumulative = currCumulative;
        for (int i = adv_time_int; i < play_time_int; i++) {
            currCumulative += viewMarks[i] - viewMarks[i - adv_time_int];
            if (currCumulative > maxCumulative) {
                maxCumulative = currCumulative;
                maxAtTime = i - adv_time_int + 1;
            }
        }
        
        return intTimeToString(maxAtTime);
    }
}

복기

1. 항상 문제를 풀기 전에 꼭 문제에 대한 이해가 선행되어야 한다!
   
   1. 처음에 최대 누적 시간이 아닌, 최대 시청 인원으로 답을 적은 점
   2. 종료 시간은 누적 시간에 포함되지 않는 점