[프로그래머스/Java] 72414번 광고 삽입

프로그래머스 광고 삽입 [2021 KAKAO BLIND RECRUITMENT]
https://programmers.co.kr/learn/courses/30/lessons/72414

누적합 알고리즘을 떠올리고 나면 생각보다 구현이 어렵지 않으나, 두 가지 포인트에 주의해야 한다.

1. 시간대 별 누적 play 횟수를 array로 관리한다면, index i를 어떤 목적으로 쓸 것인가? i-1초부터 i초까지 재생된 것을 나타낼 것인지, i부터 i+1초까지 재생된 것을 나타낼 것인지 명확하게 정의하고 구현해야 한다. 생각보다 헷갈릴 수 있다. (나의 경우 i-1초부터 i초까지 재생된 횟수로 정의하였다)
2. logs의 크기는 300,000 이하이다. 시간대 별 play 횟수의 max값은 300,000이 되겠지만, 구간 별 누적 play 횟수의 max값은 300,000*100*60*60 = 108,000,000,000회이다. Integer가 수용가능한 범위를 훨씬 넘어선다. 타입 정의에 주의하자.

.
.

문제 구현은 크게 두 단계로 나뉜다.

1. 시간대 별 play 횟수를 구하고,
2. adv_time의 길이와 일치하는 구간 별 누적 play 횟수를 세어, 그 중 Max가 되는 가장 빠른 구간을 찾는다.

나의 경우, 1번과 2번 절차에 모두 누적합 알고리즘을 적용했다.

for문을 돌며 playCount[i] += playCount[i-1]; 하는 코드가 두 번 작성되었는데,
첫번째 for문은 시간대 별 play 횟수를 구하기 위한 것이고, 두번째 for문은 0초부터 i초까지의 누적 play횟수를 구하기 위한 것이다.
이렇게 완성된 playCount를 가지고 i초부터 i+adv_time까지의 누적 재생횟수를 간단히 구할 수 있다.
(playCount[i+advSeconds] - playCount[i])

다만, 2번에서는 누적합 알고리즘 대신 투포인터 알고리즘을 적용하길 권장한다.

투포인터 알고리즘이 결코 어렵지 않을 뿐더러, 누적합을 위해 playCount를 long array로 선언해야 한다.
투포인터로 대체한다면 playCount를 integer array로 선언하고, 누적합을 일시적으로 담는 변수만 long으로 선언해 사용할 수 있다.

class Solution {
    public String solution(String play_time, String adv_time, String[] logs) {
        int playSeconds = timeToSeconds(play_time.split(":"));
        int advSeconds = timeToSeconds(adv_time.split(":"));

        long[] playCount = new long[playSeconds+1];

        for(String log : logs){
            String[] times = log.split("-");
            playCount[timeToSeconds(times[0].split(":"))+1]++;
            int endSeconds = timeToSeconds(times[1].split(":"));
            if(endSeconds+1 <= playSeconds) playCount[endSeconds+1]--;
        }

        for(int i = 1 ; i <= playSeconds ; i++)
            playCount[i] += playCount[i-1];
        for(int i = 1 ; i <= playSeconds ; i++)
            playCount[i] += playCount[i-1];

        long maxCountSum = -1;
        int answer = 0;

        for(int i = 0 ; i <= playSeconds - advSeconds ; i++){
            long countSum = playCount[i+advSeconds] - playCount[i];
            if(countSum > maxCountSum){
                maxCountSum = countSum;
                answer = i;
            }
        }
        return secondsToString(answer);
    }
    public int timeToSeconds(String[] time){
        return Integer.parseInt(time[0])*3600 + Integer.parseInt(time[1])*60 + Integer.parseInt(time[2]);
    }
    public String secondsToString(int seconds){
        StringBuilder sb = new StringBuilder();
        sb.append(String.format("%02d:", seconds/3600));
        sb.append(String.format("%02d:", (seconds%=3600)/60));
        sb.append(String.format("%02d", (seconds%=60)));
        return sb.toString();
    }
}

.
.

2021년도 기출을 하나씩 풀며 느낀 건, 명확하게 알고리즘 하나만으로 정의되는 문제는 없다.
문제를 두어 단계로 나누고, 각 단계에 어떤 알고리즘을 적용할 것인지 검토해야 한다.

돌이켜보면, 알고리즘 문제를 접하던 초창기에 마음이 급해 떠오르는 대로 작성한 뒤 틀리는 경우가 있었다.
이번 문제들은 더욱이 꼼꼼히 설계하고 접근해야 시간 낭비와 불필요한 코드 작성을 막을 수 있겠다는 생각이 든다.