(2021 카카오) 광고삽입 JAVA

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

문제를 통해 배울점은 두가지였다.

 

1. 구간합 : 투 포인터 알고리즘(Deque와 같음)

2. 누적합의 최적화

 

---

1. 구간합 : 투 포인터 알고리즘(Deque와 같음)

 

먼저 일정한 길이의 구간을 계속해서 더해야 될때의 투포인터 알고리즘을 설명해보겠다.

 

아래와 같이 구간의 길이가 3이락 할때, 구간의 합이 최대인 구간을 구하려고 한다.

=> 전에 구한 구간합에서 가장 첫 원소를 빼고 다음 원소 하나를 더해주면 다음 구간합과 같다.

 

위 알고리즘을 적용한코드는 아래와 같다.

 //Deque처럼 이전값의 맨앞값 빼고 새로운값 더하기
        for(int i=advTime; i<playTime; i++){//sum구하기
            long sum=before;
            sum-=arr[i-advTime];//이전값 빼고,
            sum+=arr[i];//새로운값 더해주기

            if(sum>max){//최대값 비교
                max=sum;
                maxStartTime=i-advTime+1;
            }
            before=sum;
        }

---

2. 누적합의 최적화

 

누적합의 최적화를 진행하지 않으면 O(N*M)이 나온다.

 for (int i = 0; i < logs.length; i++) {
            String[] s = logs[i].split("-");
            int start = convert(s[0]);
            int end = convert(s[1]);


            for(int j=start; j<end; j++) arr[j]++;
           
        }

위 코드는 참고용으로 각각의 for문에 대하여 계속해서 해당 인덱스의 배열에 더해주는것이다.

 

반면 최적화를 위해 start index값의 배열에 +1을 해주고

end index배열에 -1을 해주면 아래와 같이 표시가 된다.

다음으로 전체 배열을 순회하면서 이전 배열의 값을 누적하였는데 이렇게 하면 현재 동영상을 시청하고 있는 사람의 수가 저장된다. 

 

이를 통해 계속 배열을 매번 더해주는것이아니라 한꺼번에 for문을 더해주는 방식으로 진행하면 최적화가 된다.

 for (int i = 0; i < logs.length; i++) {
            String[] s = logs[i].split("-");
            int start = convert(s[0]);
            int end = convert(s[1]);


            //for(int j=start; j<end; j++) arr[j]++;
            arr[start]++;
            arr[end]--;
        }
        for(int i=1; i<=playTime; i++) arr[i] += arr[i-1];

 

 

결과 코드

class Solution {
    int convert(String time) {
        String[] nums = time.split(":");
        return Integer.parseInt(nums[0]) * 60 * 60
                + Integer.parseInt(nums[1]) * 60
                + Integer.parseInt(nums[2]);
    }

    public String solution(String play_time, String adv_time, String[] logs) {
        int advTime = convert(adv_time);
        int playTime = convert(play_time);
        long[] arr = new long[playTime + 1]; //단위시간만큼 배열길이

        for (int i = 0; i < logs.length; i++) {
            String[] s = logs[i].split("-");
            int start = convert(s[0]);
            int end = convert(s[1]);


            //for(int j=start; j<end; j++) arr[j]++;
            arr[start]++;
            arr[end]--;
        }
        for(int i=1; i<=playTime; i++) arr[i] += arr[i-1];


        long before=0;
        long maxStartTime=0;
        for(int i=0; i<advTime; i++) before+=arr[i];//초기값

        long max=before;

        //Deque처럼 이전값의 맨앞값 빼고 새로운값 더하기
        for(int i=advTime; i<playTime; i++){//sum구하기
            long sum=before;
            sum-=arr[i-advTime];
            sum+=arr[i];

            if(sum>max){
                max=sum;
                maxStartTime=i-advTime+1;
            }
            before=sum;
        }

        return String.format(
                "%02d:%02d:%02d", maxStartTime / (60 * 60),
                (maxStartTime / 60) % 60,
                maxStartTime % 60);
    }
}