[프로그래머스] 광고 삽입(Java, Lv3, 카카오, 누적합)

programmers.co.kr/learn/courses/30/lessons/72414

코딩테스트 연습 - 광고 삽입

 

 

 

##  접근방법

---

광고를 삽입해서, 가장 많은 시간이 누적되도록 하는 구간을 찾아야 한다. 시청자들의 출입에 관한 로그 정보들이 있다. 출입에 관한 로그 정보들을 이용해서, 1초동안 누적된 시간들을 구할 수 있다.

 

 

 

만약에 1초에 시청을 시작하고, 10초에 시청을 종료한다고 생각해보자. 

 

 

 

1초의 순간에 한 명이 증가(+)했고, 10초의 순간에 한 명이 감소(-)해야 한다. 위의 방식으로, 로그들에 대해서 처리를 해줘야 한다. 플레이 타임에 해당하는 길이만큼의 배열을 만들고, 이 배열에 로그들의 정보를 기록한다.

 

 

 

로그들의 시작과 종료를 이용해서, 특정 t초에서 t + 1초 사이에 시청하고 있는 1초 시간들의 합을 구할 수 있다. 시간의 단위는 1초이기 때문에, t초에서 t + 1초 사이가 정의된다.

 

 

 

이제 배열은 1초동안 누적된 시간을 의미한다. 특정 시간대에 누적 시청 재생시간은, (1초 * 누적 시간)들의 합과 같다. 매번 합을 구하는것보다, 누적합을 이용해서 O(N)만에 모든 값을 구해놓을 수 있다.

 

 

 

이제, 필요한 모든 정보들은 배열에 표기가 되어 있고 모든 가능 시간대를 확인하며 누적 시청 재생 시간을 구해야 한다. 어떤 광고 종료 시간이 T라고 했을 때, 누적합(T) - 누적합(T - adv_time)은 실질적으로 T - adv_time + 1 ~ T + 1 사이의 누적 시청 재생 시간을 의미하며, 시작 시간은 T - adv_time + 1이 된다.

 

 

 

위의 계산을 이용해서, 누적 시청 재생 시간 최대를 구해주면 된다.

 

 

## 해설코드

---

class Solution {
    int convertTime(String time){
        String[] sArr = time.split(":");
        return 3600 * Integer.valueOf(sArr[0]) + 60 * Integer.valueOf(sArr[1]) + Integer.valueOf(sArr[2]);
    }
    
    String convertTime(int time){
        int hour = time / 3600;
        time %= 3600;
        int min = time / 60;
        time %= 60;
        int sec = time;
        
        StringBuilder sb = new StringBuilder("");
        if(hour < 10) sb.append("0");
        sb.append(Integer.valueOf(hour));
        sb.append(":");
        
        if(min < 10) sb.append("0");
        sb.append(Integer.valueOf(min));
        sb.append(":");
        
        if(sec < 10) sb.append("0");
        sb.append(Integer.valueOf(sec));
        
        return sb.toString();
    }
    
    public String solution(String play_time, String adv_time, String[] logs) {
        String answer = "";
        long[] arr = new long[convertTime(play_time) + 1];
        
        for(int i = 0; i < logs.length; i++){
            String[] sArr = logs[i].split("-");
            
            int start = convertTime(sArr[0]);
            int end = convertTime(sArr[1]);
            
            arr[start]++;
            arr[end]--;
        }
        
        for(int i = 1; i < arr.length; i++)
            arr[i] += arr[i - 1];
        
        for(int i = 1; i < arr.length; i++)
            arr[i] += arr[i - 1];
        
        int adtime = convertTime(adv_time);
        long maxRet = arr[adtime - 1];
        int maxTime = 0;
        
        for(int i = adtime; i < arr.length; i++){
            if(maxRet < arr[i] - arr[i - adtime]){
                maxRet = arr[i] - arr[i - adtime];
                maxTime = i - adtime + 1;
            }
        }
        
        return convertTime(maxTime);
    }
}