[구간합] [프로그래머스 광고삽입] 구간합 알고리즘의 활용과 사전 작업의 이해

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

프로그래머스

프로그래머스 LV3 광고 삽입 문제를 풀다가 구간합 알고리즘을 활용하던 중 버벅거린 부분에 대해서 수학적인 이해를 하고자 정리함.

 

시청자의 영상 시청 시각 원본 데이터

위의 그래프에서 가로 선분은 영상이 재생되고 있음을 의미한다. 문제는 가장 시청자가 많은 구간을 구하는 것으로, 단순히 생각하면 모든 초단위 구간에 대해서 계산하면 되지만, 말도 안되는 시간복잡도를 가진 해결방법이다.

이때 떠올리면 좋은 풀이가 바로 구간합 알고리즘!

 

구간합 알고리즘은, 합계를 구하고 싶은 범위가 대개 일정할 때, 범위를 구하고 싶은 양 끝점을 각각 l, r 이라고 할 때, 구간이 1씩 오른 쪽으로 이동한다면 현재구간의 합계에서 l일때의 값을 빼고, r+1일 때의 값을 더하여 l~r 구간합에서 l+1~r+1의 구간합을 빠르게 계산하여 모든 가능한 구간의 합을 조사하는 알고리즘이다.

 

하지만 내가 위의 내용만 기억했다가 실전에서 문제를 못 푼 적이 있었는데, 구간의 양 끝 점을 최소 단위 1 씩 이동하며 계산하고자 하는 합계(문제에서는 해당 구간의 총 시청시간의 합계)의 증가 감소를 직접 계산하려고 하니까 복잡해졌었다.

 

그래서 구간합 알고리즘을 적용하기 전 준비 단계에 대해서 자세히 정리해보고자 함

어쨌든 위의 데이터 원형 그대로의 그래프로는 아무것도 할 수 없다.

현재 x초 일때 영상을 몇명이 시청하고 있는지를 아는 것이 중요하므로, 위의 데이터를 가지고 아래와 같이 언제 시청자수가 증가하는지, 감소하는지를 확인할 수 있는 f' 함수의 역할을 하는 그래프를 만든다 (실제 코딩할때는 배열)

이제 이 f'그래프를 적분하면 시간별 시청자수의 정보를 담고 있는 f 그래프가 나올텐데, 이는 배열을 누적합하는것으로 구현할 수 있다.

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

 

(파란색으로 표시한 부분은 시청자 수가 가장 많은 구간을 찾기 위해 정의된 구간의 길이이다.)

위의 그래프는 각 시간별 시청자의 수가 되고, 이를 실수 x에 대해서 적분하면 x=a, b 를 자른 선을 기준으로 하는 도형의 넓이를 구할 수 있지만, 문제의 조건 상 1초 단위로만 시청자 수의 추가와 감소가 일어나므로 구간의 넓이의 최대값을 찾기 위해서 실수 x에 대해서 정적분 할 필요가 없다.  

왜냐하면? 정의역이 실수 x에 대해서 정의된 것이 아니라 0이상의 정수에 대해서만 정의되어있기 때문

1초 단위의 초록색 선

이해를 돕기 위해 막대 그래프를 그렸지만, 실제 계산과 컴퓨터가 이해하기로는 초록색 선분으로 현재 상황을 이해하고 있다고 생각하면 편하다.

빨간색 화살표 : 고려하지않아도 되는 부분

초록색 선분 이외의 구역은 생각 하지 않아도 되고, 생각하지 않아야 하며, 이 떄문에 정적분과 아이디어는 유사하나, 사실은 수열의 합으로 계산하게된다.

 

 

따라서 아이디어는 아래와 같은 함수를 생각하면 되고,(정적분과는 엄연히 다르므로 옳은 표현은 아니다.)

$$ \int f(x) dx \ =\ F(x) \ \ where\ \ x = 1,2,3 ··· $$

 

 

실제로 계산할 때는 정수점( 문제에서 조건으로 제시한 최소의 단위)을 대입하여 아래와 같은 수식을 계산하면 된다.

$$ F(b) \ - \ F(a) \ \ where \ \ a,b = 1,2,3$$ ··· 

그러므로 엄연히 말하면 정적분은 아니고 수열의 합과 비슷하다.

여태까지의 내용을 정리해서 결국 내가 하고 싶은 것은 정수점에 대해서 함수값을 누적으로 합하여 x=(a,b) 의 구간 사이의 x가 정수일 때의 함수값의 총 합을 계산하고 싶어서 아래와 같은 함수를 정의하여

$$ F(x) = \Sigma ^{x} _{k=0,1,2,3...} f(k)$$

 

$$ F(b)\ -\ F(a)$$ 위의 값을 구간합으로 사용하는것이다.

 

만들어진 F(x)는 아래의 그래프와 같다고 이해하면 된다.

많이 생략함..

 

아래는 풀이 전체

import java.util.*;
import java.util.stream.*;
class Solution {
    public String intToTimeString(int timeInt){
        int hour = timeInt / (60 * 60);
        timeInt %= (60*60);
        int min = timeInt / 60;
        timeInt %= 60;
        int sec = timeInt;
        return String.format("%02d:%02d:%02d", hour, min, sec);
        
    }
    public int timeToInt(String time){
        int hour = Integer.parseInt(time.substring(0,2));
        int min = Integer.parseInt(time.substring(3,5));
        int sec = Integer.parseInt(time.substring(6,8));
        int timeInt = (hour * 60 * 60) + (min * 60) + sec;
        return timeInt;
    }
    public String solution(String play_time, String adv_time, String[] logs) {
        String answer = "";
        int len = logs.length;
        // 전체 시간이 100시간으로 100 * 60 * 60, 즉 360000초가 검사해야할 가능한 전체 구간의 최대 길이이다.
        // 배열의 크기로써 충분하므로 구간합 문제로 구할 수 있다.
        int playTimeSec = timeToInt(play_time);
        int interval = timeToInt(adv_time);
        
        long[] times = new long[playTimeSec+1];
        
        for(int i = 0 ; i < len; i++){
            int addViewerTime = timeToInt(logs[i].substring(0,8));
            int removeViewerTime = timeToInt(logs[i].substring(9,17));
            times[addViewerTime] ++;
            times[removeViewerTime] --;
        }
        //times 배열은 현재 f' 역할 언제 시청자수가 증가 감소하는지 나타냄
        
        for(int i = 1 ; i < times.length; i++){
            times[i] += times[i-1];
        }
        // times 배열은 현재 f 역할, 어떤 시각 i에서 시청자수가 몇명인지 나타냄
        
        for(int i = 1 ; i < times.length; i++){
            times[i] += times[i-1];
        }
        
        // times 배열은 현재 F 역할, 시각 i=0부터 어떤 i=t 까지의 총 누적 시청자수를 계산,
        
        long maxPlayTime =times[interval]; 
        int startTime = 0;
        
        for(int time = 0; time + interval < times.length; time++){
            // F(t+interval) - F(t) 최대인 t를 찾는다. 
            if(maxPlayTime < times[time + interval] - times[time])
            {
                
                startTime = time+1;
                maxPlayTime = times[time + interval] - times[time];
            }
        }
        
        return intToTimeString(startTime);
        
        
        
    }
}