프로그래머스 - 광고 삽입

leehyunjon·2022년 5월 2일

Algorithm

목록 보기

20/162

광고 삽입 : https://programmers.co.kr/learn/courses/30/lessons/72414

Problem

Solve

추석 트래픽 문제를 풀고나서 신나서 시간문제에 호기롭게 시작했다가 멘탈이 나가버린 문제.
해당 문제는 구간합 알고리즘또는 투 포인터 알고리즘을 이용해 풀수 있는 문제라고 한다.
두가지 방법 모두 해보려고 했으나. 투 포인터는 좀 더 공부한 후 다시 돌아오기로 했다..

구간합 알고리즘을 사용하기 위해서는 사용할 수 있는 배열의 크기가 360000인것을 파악해야 접근할 수 있다.
자세한 풀이방법은 바킹독님의 정성스러운 풀이를 참고하자(https://blog.encrypted.gg/995?category=916869)

문제 풀이 순서는 아래와 같다.

play_time을 int로 변환한 뒤 구간합에 사용할 시간 배열(accumulateTime)의 크기로 사용한다.(최대 100시간 미만의 play_time을 가질수 있으므로 1006060 = 360000의 크기)
배열 accumulateTime의 index를 시간으로 생각하고 logs의 각 시작시간과 끝시간을 int로 변환한 뒤 accumulateTime[시작시간] += 1, accumulateTime[끝시간] -= 1을 해준다.
+1은 해당 시간(index)에 동영상을 재생한 사람이 1명 누적되는것, -1은 해당 시간에 동영상을 재생한 사람이 1명 빠지게 되는것.
예를 들어

예시 문제1에 log에 '01:37:44 - 01:45:14'가 있다면 각각 int로 변환하면 5864, 6314가 된다.
이를 위에 설명했던 식으로 적용하면 '01:37:44'에는 누적 인원이 3명, '01:45:14'에는 누적 인원이 2명이 남게 되는것이다.
위 식을 적용해보면 대강 아래와 같은 배열이 만들어 질것이다.
누적 인원의 가중치로 저장되어있는 accumulateTime배열을 누적 인원으로 변경시켜준다.
변경 시켜주면 아래와 같은 배열로 갱신될것이다.
시작 시간부터 adv_time까지의 합을 구해준다.
초기 합을 바탕으로 구간 합을 사용해서 광고 시간의 범위를 이동시켜주며 최대의 누적 인원이 나온 광고 시작시간을 저장한다.시간 범위에 있는 누적 인원의 합을 구하는 것이라 누적 시간과 비례한다.
이렇게 누적합을 사용해주면 이중for문으로 i,j를 이용해서 광고 시간 범위에 있는 누적합을 구하는 최대 O(360000*360000)보다 i하나로 최대 O(360000+360000)을 만들어 낼수 있다.
최대 누적인원의 합을 가지는 광고 시작 시간 반환.

Code

class Solution {
    public String solution(String play_time, String adv_time, String[] logs) {
        //누적 인원 저장 배열
        int[] accumulateTime = new int[360001];
        int advTime = timeToint(adv_time);
        int playTime = timeToint(play_time);
        //누적 인원 가중치 초기화
        for(String log : logs){
            String[] logTimes = log.split("-");
            int startTime = timeToint(logTimes[0]);
            int endTime = timeToint(logTimes[1]);
            
            accumulateTime[startTime] += 1;
            accumulateTime[endTime] -= 1;
        }
        
        int s=0;
        //누적 인원
        for(int i = 0;i<accumulateTime.length;i++){
            s += accumulateTime[i];
            accumulateTime[i] = s;
        }
        
        int maxIdx=0;
        long maxSum=0;
        long sum=0;
        //광고 범위의 누적인원 합 초기화
        for(int i=0;i<advTime;i++){
            sum+=accumulateTime[i];
        }
        maxSum = sum;
        
        //누적 인원의 합을 누적합으로 갱신
        for(int i=advTime;i<=playTime;i++){
            sum += accumulateTime[i]-accumulateTime[i-advTime];

			//누적 인원의 합이 기존 누적합보다 크다면 누적합과 광고 시작 시간 갱신
			if(maxSum<sum){
                maxSum = sum;
                maxIdx = i-advTime+1;
            }
        }
        
        return timeTostring(maxIdx);
    }
    
    //int_time to string_time
    String timeTostring(int time){
        int h = time/3600;
        time %= 3600;
        int m = time/60;
        time %= 60;
        int s = time;
        
        StringBuilder sb = new StringBuilder();
        if(h<10) sb.append("0");
        sb.append(h);
        sb.append(":");
        if(m<10) sb.append("0");
        sb.append(m);
        sb.append(":");
        if(s<10) sb.append("0");
        sb.append(s);
        
        return sb.toString();
    }
    
    //string_time to int_time
    int timeToint(String time){
        String[] arr = time.split(":");
        int h = Integer.parseInt(arr[0])*60*60;
        int m = Integer.parseInt(arr[1])*60;
        int s = Integer.parseInt(arr[2]);
        
        return h+m+s;
    }
}