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

문제 설명

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

문제 풀이

• 구간합을 이용하여 풀이하였다.

• 문제는 다음과 같은 방향으로 풀이하였다.

  1. 시간 배열을 두고 각 시간에 시청자 수를 구한다.
  2. 가능한 범위를 순회하면서 특정 구간에 시청자 수 합의 최대값을 구한다.

• 여기서 문제는 위 두 케이스를 단순하게 구현한다면 결과를 구하기위한 시간복잡도는 약 30만 * 30만으로 시간초과가 발생한다.

• 이를 해결하기위해 각각 아래와 같이 구간합을 이용하여 구한다.

  1. 시간 배열을 두고 각 시간의 시청자 수 구하기
     - 각 시청자 수의 시작지점에 + 1, 종료지점에 -1을 해준다. -> O(1)
     - 이후 누적합을 구하면 특정 시간의 시청자 수 배열이 완성된다. -> O(시간범위)
  2. 가능한 시간 범위를 순회하며 해당 구간의 시청자 수 합의 최대값 구하기
     - 우선 1에서 만들어진 배열의 누적합 배열을 만들어 준다.
     - 가능한 시간 범위를 순회하며 아래 작업을 수행한다. -> O(시간범위)
     - 각 구간의 시청자수 합은 종료지점에서 누적합배열값 - 시작지점에서 누적합배열값 -> O(1)

• 위처럼 누적합을 이용해 각 작업의 시간 복잡도를 낮춰서 풀이하였다.

소스 코드 (JAVA)

import java.util.*;

class Solution {

    public int convertStringToNum(String time) {
        StringTokenizer st = new StringTokenizer(time, ":");
        int hour = Integer.parseInt(st.nextToken());
        int min = Integer.parseInt(st.nextToken());
        int sec = Integer.parseInt(st.nextToken());
        return hour * 3600 + min * 60 + sec;
    }

    public String convertNumToString(int time) {
        StringBuilder sb = new StringBuilder();
        int hour = time / 3600;
        if (hour < 10) sb.append("0");
        sb.append(hour);
        sb.append(":");
        time -= hour * 3600;
        int min = time / 60;
        if (min < 10) sb.append("0");
        sb.append(min);
        sb.append(":");
        time -= min * 60;
        if (time < 10) sb.append("0");
        sb.append(time);
        return sb.toString();
    }

    public String solution(String play_time, String adv_time, String[] logs) {
        int endTime = convertStringToNum(play_time);
        int duration = convertStringToNum(adv_time);
        long[] arr = new long[endTime + 1];
        long[] sum = new long[endTime + 1];
        long[] ssum = new long[endTime + 1];
        //시간 배열 세팅 (각 시간별 인원수)
        //1. 시작 시간에 1, 종료시간에 -1 찍어줌
        for (int i = 0; i < logs.length; i++) {
            StringTokenizer st = new StringTokenizer(logs[i], "-");
            arr[convertStringToNum(st.nextToken())]++;
            arr[convertStringToNum(st.nextToken())]--;
        }
        //2. 구간합 구하면 특정 시간에 특정 인원 수 배열이 됨
        int tmpInt = 0;
        for (int i = 0; i <= endTime; i++) {
            tmpInt += arr[i];
            sum[i] = tmpInt;
        }
        //3. 여기에 구간합 구하면 특정 구간 인원 수를 O(1)에 구할 수 있음
        long tmpLong = 0;
        for (int i = 0; i <= endTime; i++) {
            tmpLong += (long)sum[i];
            ssum[i] = tmpLong;
        }

        //4. 각 시작 지점에서 구간합 비교
        long max = 0;
        int maxTime = 0;
        for (int i = 0; i <= endTime - duration; i++) {
            long tmp = ssum[i + duration - 1];
            if (i != 0) tmp -= ssum[i-1];
            if (tmp > max) {
                max = tmp;
                maxTime = i;
            }
        }

        return convertNumToString(maxTime);
    }
}