[프로그래머스][Java] 광고 삽입

1. 문제 정보

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

프로그래머스

난이도 : 3

유형 : 누적합

시간 : 선형

---

2. 문제 풀이

프로그래머스 문제답게 문자열로 주어진 입력값을 처리하는 게 번거롭다.

 

이 문제의 핵심은 누적합을 범위로 처리하는 것이다.

 

logs 배열을 쿼리라고 생각하면서 각 구간마다 경계에서 증감 연산을 누적합 배열에 적용한다.

(매 쿼리마다 시작 시간부터 끝나는 시간까지 직접 반복문을 돌면서 구간을 업데이트 하는 것은 비효율적이며, 최대 play_time ^ 2의 시간이 걸릴 수 있다.)

---

3. 코드

class Solution {

    public long[] prefixSum;

    public int[] convertLogToSecond(String log) {
        String[] logSplit = log.split("-");
        return new int[]{convertTimeStringToSecond(logSplit[0]), convertTimeStringToSecond(logSplit[1])};
    }

    public int convertTimeStringToSecond(String time) {
        String[] dateTime = time.split(":");
        return Integer.parseInt(dateTime[0]) * 3600 + Integer.parseInt(dateTime[1]) * 60 + Integer.parseInt(dateTime[2]);
    }

    public String solution(String play_time, String adv_time, String[] logs) {
        prefixSum = new long[360001];

        for (String log : logs) {
            int[] secondInfo = convertLogToSecond(log);
            prefixSum[secondInfo[0]]++;
            prefixSum[secondInfo[1]]--;
        }

        for (int i = 1; i < prefixSum.length; i++) {
            prefixSum[i] = prefixSum[i - 1] + prefixSum[i];
        }
        for (int i = 1; i < prefixSum.length; i++) {
            prefixSum[i] = prefixSum[i - 1] + prefixSum[i];
        }

        int playTime = convertTimeStringToSecond(play_time);
        int advTimeSecond = convertTimeStringToSecond(adv_time);
        long max = prefixSum[advTimeSecond - 1];
        int minStartTime = 0;

        for (int i = advTimeSecond; i <= playTime; i++) {
            long rangeSum = prefixSum[i] - prefixSum[i - advTimeSecond];
            if (rangeSum > max) {
                max = rangeSum;
                minStartTime = i - advTimeSecond + 1;
            }
        }

        int resHour = minStartTime / 3600;
        int resMin = (minStartTime % 3600) / 60;
        int resSec = minStartTime % 60;

        StringBuilder sb = new StringBuilder();
        sb.append(String.format("%02d", resHour)).append(":").append(String.format("%02d", resMin)).append(":").append(String.format("%02d", resSec));
        return sb.toString();
    }
}