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

이 문제는 누적 합을 이용해서 풀었다.

 

누적 합은 길이가 n인 arr 배열이 있다고 했을 때 sum[i] = arr[0....i] 까지의 합 으로 정의하여 구간 합을 빠르게 구하기 위한 테크닉이다.

 

누적 합을 이용한 테크닉이 하나 있는데 만약 i 부터 j 까지 전부 1을 더하고 싶을 경우 반복문으로 하는 것이 아닌 arr[i]++, arr[j + 1]-- 을 적용하고 나중에 일괄적으로 누적 합을 계산하면 원하는 결과가 나오는 방법이 있다.

이 방법을 사용하면 반복문으로 매번 하는 것보다 시간 복잡도가 많이 개선된다. 매 루프마다 정해진 구간에 반복문을 수행하는 게 아닌 나중에 일괄적으로 처리할 수 있기 때문이다.

 

이 문제 또한 이 방법을 생각하는 것이 핵심이었다. 그러나 이 방법으로 정답이 나오지 않아 카카오 해설을 보았고 누적 합을 동일하게 사용하지만 구간 마지막을 포함하지 않는 범위로 값이 추가되는 것을 발견하였다.

 

문제를 보면 어떤 구간의 끝과 다른 구간의 시작이 동일할 때, 각기 다른 카운트가 적용된다. 그래서 마지막 구간을 포함하도록 문제를 풀면 정답이 아예 나오지 않는다. 

 

약간의 추측을 하자면 마지막 구간과 시작 구간이 겹칠 때의 케이스가 어렵기 때문에 일부러 마지막 구간이 겹치지 않게 만들어놓으면 문제가 더 쉽게 바뀌는 것으로 생각했다.

 

카카오 기출에서 한번씩 누적 합 문제를 출제하므로 꼭 기억해야겠다.

import java.util.*;
import java.io.*;

class Solution {
    
    static final int INF = 1000000000;
    
    int[] timeTable;
    int interval;
    int allTime;
    
    public String solution(String play_time, String adv_time, String[] logs) {
        allTime = toSecond(play_time);
        interval = toSecond(adv_time);
        timeTable = new int[allTime + 3];
        
        for (final String log : logs) {
            final StringTokenizer st = new StringTokenizer(log, "-");
            
            final int start = toSecond(st.nextToken());
            final int end = toSecond(st.nextToken());
            
            timeTable[start]++;
            timeTable[end]--;
        }
        
        bulk();
        
        final int result = findAnswer();
        
        final String answer = toTime(result);
        
        return answer;
    }
    
    void bulk() {
        for (int i = 0; i <= allTime; i++) {
            timeTable[i + 1] += timeTable[i];
        }
    }
    
    int findAnswer() {
        int start = 0;
        int end = interval - 1;
        
        int index = 0;
        long temp = calculate(start, end);
        long dist = temp;
        
        while (end <= allTime - 1) {
            dist -= timeTable[start];
            start++;
            
            end++;
            dist += timeTable[end];
            
            if (end <= allTime - 1) {
                if (dist > temp) {
                    index = start;
                    temp = dist;
                }
            }
        }
        
        return index;
    }
    
    long calculate(final int start, final int end) {
        long result = 0;
        
        for (int i = start; i <= end; i++) {
            result += timeTable[i];
        }
        
        return result;
    }
    
    int toSecond(final String time) {
        final StringTokenizer st = new StringTokenizer(time, ":");
        
        final int hour = Integer.parseInt(st.nextToken());
        final int minute = Integer.parseInt(st.nextToken());
        final int second = Integer.parseInt(st.nextToken());
        
        return hour * 3600 + minute * 60 + second;
    }
    
    String toTime(final int second) {
        StringBuilder sb = new StringBuilder();
        int temp = second;
        
        final int hour = temp / 3600;
        temp %= 3600;
        sb.append(format(hour));
        
        sb.append(":");
        
        final int minute = temp / 60;
        temp %= 60;
        sb.append(format(minute));
        
        sb.append(":");
        
        final int sec = temp;
        sb.append(format(sec));
        
        return sb.toString();
    }
    
    String format(final int temp) {
        final String result = String.valueOf(temp);
        
        if (result.length() == 1) {
            return "0" + result;
        }
        return result;
    }
}