[Algorithm] 프로그래머스 - 광고 삽입 자바 풀이

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

 

이번 포스팅은 프로그매러스 광고 삽입 자바 풀이를 작성하고자 합니다.

 

문제 출처:  https://school.programmers.co.kr/learn/courses/30/lessons/72414#

프로그래머스

 

 

1. 풀이 소스 

 

import static java.lang.Integer.parseInt;

class Solution {
    public String solution(String play_time, String adv_time, String[] logs) {
        
        if (play_time.equals(adv_time)) return "00:00:00";

        int[] allTime = new int[getSecondsTime(play_time) + 1]; // 00:00:00 ~ 00:00:02은 2개의 배열 공간 필요
        
        for (String log : logs) {
            String[] times = log.split("-");
            String sTime = times[0];
            String eTime = times[1];
            
            int start = getSecondsTime(sTime);
            int end = getSecondsTime(eTime);
            
            allTime[start] += 1; // 누적합을 위한 시작 지점 
            allTime[end] -= 1; // 누적합을 위한 마지막 지점에 -1  // 00:00:00 ~ 00:00:02 [1, 1, 0] (00:00 ~ 00:01, 00:00)
        }
        
        for (int i = 1; i < allTime.length; i++) {
            allTime[i] = allTime[i - 1] + allTime[i]; // 이전항에 누적합으로 더함 (00:00:00 ~ 00:00:10)
        }     
        
        int advTime = getSecondsTime(adv_time); // 00:00:00 ~ 00:00:02 (2초)
        long sum = 0;
        
        for (int i = 0; i < advTime; i++) { // advTime이 2초 하면 
            sum += allTime[i];  // ex) 0초부터 ~ 2초까지 누적합을 계산 [1, 1, 0] -> 2
        }
                
        int idx = advTime; // 시작점을 advTime 으로 설정 (2)
        long maxSum = sum; // 가장 큰 토탈 시간
        int startPoint = 0; // 가장 큰 토탈 시간에 맞는 포인트 
        int startCnt = 0; // 누적합에서 포인터를 이동시킬 cnt
        
        // idx = 3, 3초까지의 누적합 0 ~ 1초까지의 누적합 
        for (int i = idx; i < allTime.length; i++) {
            
            sum = sum + allTime[i] - allTime[startCnt]; 
            startCnt++; // 누적합에서 빠진 인덱스이므로 시작 포인트를 위해 ++
            
            if (maxSum < sum) {
                maxSum = sum;
                startPoint = startCnt; // 시작점은 누적합에 포함되기 시작한 (= 누적합에서 빠진 마지막 인덱스)   
            }
        }
        
        return getTime(startPoint);
    }
    
    private int getSecondsTime(String times) {
        String[] time = times.split(":");
        return parseInt(time[0]) * 60 * 60 + parseInt(time[1]) * 60 + parseInt(time[2]);
    }
    
    private String getTime(int point) {
        int hour = point / 3600;
        int minute = (point % 3600) / 60;
        int seconds = (point % 3600) % 60;
            
        return getStringTime(hour) + ":" + getStringTime(minute) + ":" + getStringTime(seconds);
    }
    
    private String getStringTime(int time) {
        String result = "";
        if (time < 10) result = "0" + String.valueOf(time);
        else result = String.valueOf(time);
        return result;
    }
}

 

 

2. 풀이 과정

 

해당 문제는 이전에 풀었던 문제인 누적합 개념을 적용하면 보다 빠르게 해결할 수 있습니다.

누적합이란 임의의 점이 n ~ m까지 범위이고 특정 범위로 시작점 끝점이 주어질 때,

매번 for문으로 주어진 범위까지 1씩 증가하면서 반복해서 더하는 것이 아니라, 주어진 시작점과 끝점에 포인트를 기록하여 

단 한 번의 포문으로 누적합이 될 수 있도록 구현하는 방법입니다.

 

예를 들면 다음과 같습니다.

int[] point = {4, 8};
int[] arr = new int[10];

for (int i = point[0]; i <= point[1]; i++) {
    arr[i] += 1;
}


int[] arr2 = new int[10];

arr2[point[0]] += 1;
arr2[point[1] + 1] -= 1;

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

 

위의 예시는 누적합을 적용하지 않은 개념으로 범위 계산 시 매번 해당 범위사이에 있는 값을 +1 해야 합니다.

하지만 누적합은 누적할 범위 시작점에 +1, 마지막 점 + 1에 -1을 해줌으로써 누적합을 구현할 수 있습니다.

 

최종적으로 누적합을 계산하면 둘 다 5가 나옵니다. 만약 구해야 하는 point가 10만 개이고, 범위가 최대 1000만이라면
앞 서 하나씩 1을 증가시켜서 누적합을 계산하는 경우 최악은 10만 * 범위(1000만) 까지의 시간 복잡도가 나옵니다.

 

반면, 누적합을 구하는 경우 point 시작점, 끝점 계산은 2개가 소요되고, 마지막 누적합만 적용하면 되므로

2 * 10만 + 1000만의 시간 복잡도가 소모됩니다.

 

따라서, 이 원리를 적용하여 해당 문제를 해결하려면 범위 계산을 위해 각 영상 시작 시간과 종료시간을 모두 초 단위로 바꿔야 합니다. 

 

예를 들어 "01:00:00 - 01:01:00" 은 초단위로 설정하면 3600 * 1  ~ 3600 * 1 + 60 * 1입니다.

즉 영상 시작이 0초대에 시작한다고 하면 영상 시작으로 3600초 ~ 3660 사이입니다. 

 

그렇다면 해당 영상 누적 합을 위해 범위를 어떻게 설정해야 할까요?

0 ~ 1초까지의 누적시간은 1초입니다. 이 1초를 어느 위치에 선정하느냐에 따라 접근 방식이 달라질 수 있습니다.

 

저는 누적 시간이 가장 크면서 가장 빠른 시간을 구해야 하므로,

0 ~ 1초 사이의 누적합 1초는 인덱스 0에 기록하는 방법을 택했습니다.

 

즉, [0, 0, 0] (0 ~ 3초)의 영상 시간에 광고가 0 ~ 1초 동안 지속한다면, 

[1, -1, 0]로 누적합을 위한 배열 A를 설정하고, 최종 누적합으로 인한 계산은 [1, 0, 0]이 나옵니다.

 

이를 이용하여, 누적합을 계산한 후,

for문으로 다음 인덱스와 시작점 인덱스를 옮긴 후, 고정된 K 범위 내에서 가장 많은 누적시간을 기록한 startPoint를 찾습니다.

오름차순으로 for문 인덱스를 설정하는 경우 이전 maxSum과 sum을 비교하여 sum이 더 큰 경우를 찾는다면 가장 빠른 startPoint를 찾을 수 있습니다.

 

 

테스트 케이스 공유 : 

 

"99:59:59" "00:00:01" ["69:59:59-89:59:59", "01:00:00-21:00:00", "79:59:59-99:59:59", "11:00:00-31:00:00"] "11:00:00"

"00:00:10"  "00:00:09"  ["00:00:00-00:00:03", "00:00:03-00:00:04", "00:00:03-00:00:05", "00:00:09-00:00:10"]  "00:00:00"

"00:00:10"  "00:00:09"   ["00:00:01-00:00:03", "00:00:03-00:00:04", "00:00:03-00:00:05", "00:00:09-00:00:10", "00:00:09-00:00:10"] "00:00:01"

"00:00:10"  "00:00:07"  ["00:00:02-00:00:03", "00:00:03-00:00:04", "00:00:03-00:00:05"]  "00:00:00"

"00:00:10" "00:00:01" ["00:00:01-00:00:02", "00:00:03-00:00:04", "00:00:03-00:00:05"] "00:00:03"

"00:00:10" "00:00:01" ["00:00:01-00:00:02", "00:00:03-00:00:04", "00:00:02-00:00:05"] "00:00:03"

"00:00:10" "00:00:02" ["00:00:01-00:00:02", "00:00:02-00:00:04", "00:00:02-00:00:05"] "00:00:02"

"50:00:00" "49:50:00" ["15:36:51-38:21:49", "10:14:18-15:36:51", "38:21:49-42:51:45"] "00:00:00"

 

 

이상으로 해당 문제 풀이를 마치도록 하겠습니다. 감사합니다.!!