프로그래머스: 광고 삽입 [JAVA]

문제 링크

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

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

풀이

전체적인 풀이 과정은 다음과 같다.

 

1. 모든 주어진 시간 문자열을 초(second)로 변환
2. IMOS 기법을 적용해 logs 속 모든 시청 시간들을 표현
3. 영상의 시작부터 각 초까지의 누적 값 배열을 초기화
4. 영상의 시작부터 광고가 모두 틀어질 수 있는 시간까지, 반복문을 통해 특정 시작 시간 t에 대해 누적값 배열[t + 광고 시간 + 1] - 누적값 배열[t + 1] 연산으로 해당 구간의 조회총합을 계산해 최대 구간 값 도출

 이 문제에서 시간도 시간이지만, 무엇보다 조회 기록이 담긴 logs 배열이 최대 300,000만 정도가 되기 때문에 이를 활용하기 위해 정렬을 하거나 해당 조회 기록 속 시간을 일일히 체크하다보면 쉽게 시간초과가 발생할 수 있다.

 문제의 해결을 위해선 우선적으로 알아야 하는 일종의 기법이 존재하는데, 바로 IMOS 기법이다. IMOS 기법은 여러 구간의 누적을 이용해야 하는 문제에서 해당 구간의 모든 곳을 일일히 방문하거나 이를 정렬할 필요 없이 필요한 값들을 표시한 후 반복문을 통해 이런 값들을 누적시켜 필요한 결과를 얻는 방식이다.

 

 참고: https://black-hair.tistory.com/147

누적합의 확장 IMOS

 

 이런 과정에서 하나의 배열에 값들을 연속적으로 담고자, 우선 주어진 시간 문자열들을 초로 모두 변환한다. 다음 IMOS 기법을 적용하면, 모든 동영상 구간에 대해 특정 시간에서 조회 수를 구할 수 있는 배열이 만들어진다. 다만 여기선 시청 시간을 계산하는데 좀 더 직관적인 이해를 위해 IMOS 기법 상의 +1과 -1을 log 속 기록 시간 +1을 더한 지점에 표시한다.

 이후에 특정 시간부터 광고 시간만큼의 조회 수를 반복문을 통해 구간의 조회 수 총합을 구할 수도 있지만, 이를 좀 더 효율적으로 만들고자 앞선 조회 수 결과가 담긴 배열을 가공해 영상의 시작부터 해당 위치까지의 조회 수 누적값이 저장된 배열을 만든다. 해당 배열을 통해 얻을 수 있는 이득은 구간 A에서 B까지의 조회 수 총합을 구할 때 일일히 반복문을 통해 값을 계산하는게 아닌, 누적값 배열[B] - 누적값 배열 [A - 1] 연산을 적용하면 쉽게 구간의 총합을 구할 수 있다.

 그 다음에는 영상의 시작부터 광고를 모두 틀 수 있는 시간까지 반복문을 통해 광고가 최대 조회수를 받을 수 있는 구간을 계산하여 답을 도출하면 된다.

 

class Solution {
    long[] viewsAcc; //조회 수 누적값

    public String solution(String play_time, String adv_time, String[] logs) {
        StringBuilder answer = new StringBuilder();
        int playTimeSec = convertToSec(play_time), advTimeSec = convertToSec(adv_time), answerSec;//시간 변환
        long maxViews;

        viewsAcc = new long[playTimeSec + 1]; //누적값 배열 초기화

        for (int i = 0; i < logs.length; i++) { //log 분해 후 위치 표시
            String[] split = logs[i].split("-");
            int startSec = convertToSec(split[0]);
            int endSec = convertToSec(split[1]);

            ++viewsAcc[startSec + 1];

            if (endSec + 1 < viewsAcc.length) {
                --viewsAcc[endSec + 1];
            }
        }

        int nowViewer = (int) viewsAcc[0]; //해당 시간의 시청자

        for (int i = 1; i < viewsAcc.length; i++) { //누적값 배열 채우기
            nowViewer += viewsAcc[i];
            viewsAcc[i] = viewsAcc[i - 1] + nowViewer;
        }

        maxViews = viewsAcc[advTimeSec];//0초에서 +광고 시간 만큼을 답으로 미리 초기화
        answerSec = 0;

        for (int time = 1; time <= playTimeSec - advTimeSec; time++) {//혀용 범위 내에서 해당 시간대의 총 조회수 계산
            long views = viewsAcc[time + advTimeSec] - viewsAcc[time];

            if (views > maxViews) {//조회수가 더 많다면 (답이라면)
                answerSec = time;
                maxViews = views;
            }
        }

        //답 반환용 절차 (시, 분, 초 계산 및 문자열 형태 맞추기)
        int answerHour = answerSec / 3600;
        int answerMinute = (answerSec % 3600) / 60;
        int answerSecond = answerSec - answerHour * 3600 - answerMinute * 60;

        if (answerHour < 10) {
            answer.append("0");
        }
        answer.append(answerHour + ":");

        if (answerMinute < 10) {
            answer.append("0");
        }
        answer.append(answerMinute + ":");

        if (answerSecond < 10) {
            answer.append("0");
        }
        answer.append(answerSecond);

        return answer.toString();
    }

    int convertToSec(String time) {//주어진 시간 문자열 -> 초로 변환
        int h, m, s;

        String[] split = time.split(":");

        h = Integer.parseInt(split[0]);
        m = Integer.parseInt(split[1]);
        s = Integer.parseInt(split[2]);

        return 3600 * h + 60 * m + s;
    }
}

참고

 이 때 문제에서 주의해야 할 점은, 첫 번째로는 조회 수 누적값 배열의 경우 수가 크기 때문에 long 타입의 배열을 생성해야 한다는 점이다. 두 번째로는 문제에서 요구하는 A초에서 B초까지의 시청 시간 총합이 흔히들 생각하는 인덱스 A부터 인덱스 B까지의 누적 값과 다르게 값을 계산해야 한다는 점이다. 인덱스의 경우 누적값 배열[B] - 누적값 배열[A - 1]을 적용하면 되지만, 여기 문제에서 시청시간은 일종의 구간이기 때문에, 누적값 배열[B] - 누적값 배열[A]를 적용해야 올바른 시청 시간 총합을 구할 수 있다.

결과