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

문제

---

"죠르디"의 동영상 재생시간 길이 play_time, 공익광고의 재생시간 길이 adv_time, 시청자들이 해당 동영상을 재생했던 구간 정보 logs가 매개변수로 주어질 때, 시청자들의 누적 재생시간이 가장 많이 나오는 곳에 공익광고를 삽입하려고 합니다. 이때, 공익광고가 들어갈 시작 시각을 구해서 return 하도록 solution 함수를 완성해주세요. 만약, 시청자들의 누적 재생시간이 가장 많은 곳이 여러 곳이라면, 그 중에서 가장 빠른 시작 시각을 return 하도록 합니다.

 

[제한사항]

• play_time, adv_time은 길이 8로 고정된 문자열입니다.
  • play_time, adv_time은 HH:MM:SS 형식이며, 00:00:01 이상 99:59:59 이하입니다.
  • 즉, 동영상 재생시간과 공익광고 재생시간은 00시간 00분 01초 이상 99시간 59분 59초 이하입니다.
  • 공익광고 재생시간은 동영상 재생시간보다 짧거나 같게 주어집니다.
• logs는 크기가 1 이상 300,000 이하인 문자열 배열입니다.
  • logs 배열의 각 원소는 시청자의 재생 구간을 나타냅니다.
  • logs 배열의 각 원소는 길이가 17로 고정된 문자열입니다.
  • logs 배열의 각 원소는 H1:M1:S1-H2:M2:S2 형식입니다.
    • H1:M1:S1은 동영상이 시작된 시각, H2:M2:S2는 동영상이 종료된 시각을 나타냅니다.
    • H1:M1:S1는 H2:M2:S2보다 1초 이상 이전 시각으로 주어집니다.
    • H1:M1:S1와 H2:M2:S2는 play_time 이내의 시각입니다.
• 시간을 나타내는 HH, H1, H2의 범위는 00~99, 분을 나타내는 MM, M1, M2의 범위는 00~59, 초를 나타내는 SS, S1, S2의 범위는 00~59까지 사용됩니다. 잘못된 시각은 입력으로 주어지지 않습니다. (예: 04:60:24, 11:12:78, 123:12:45 등)
• return 값의 형식
  • 공익광고를 삽입할 시각을 HH:MM:SS 형식의 8자리 문자열로 반환합니다.

 

풀이

---

모든 케이스를 다돌면서 해당 케이스일 때의 누적재생시간을 구해서 구하는 방법을 사용하였더니, logs의 최대크기가 300000이나 되다보니 시간 초과가 발생하였다.

 

그래서 전체 재생시간을 기준으로 누적 재생시간을 모두 저장하여 가장 누적재생시간이 큰 구간을 찾는 방식을 사용하였다.

 

아래 나오는 코드가 핵심 코드다.

for(int i = 0 ; i < logs.length ; i++){
	int start = timeToInt(logs[i].substring(0, 8));
	int end = timeToInt(logs[i].substring(9, 17));
            
	play[start]++;
	play[end]--;
} 
        
// 누적 시청자수
for(int i = 1 ; i <= playTime ; i++){
	play[i] += play[i - 1];
}
        
// 누적 재생시간
for(int i = 1 ; i <= playTime ; i++){
	play[i] += play[i - 1];
}

각각의 log들에 대해서 재생이 시작하는 부분으 +1을, 끝나는 부분은 -1을 해주었다.

여기서 전체 재생시간은 1초를 기준으로 모두 숫자화 시켰다.

 

이렇게 된 전체재생시간 배열을 한번 돌면서 i-1 값을 누적시켜준다.

이렇게 한 번 누적하면 해당 시간에 누적 시청자 수가 저장되게 된다.

 

똑같은 방식으로 한번더 누적합을 만들어주면, 누적 재생시간이 저장되게 된다.

 

만약 아래와 같은 재생시간이 있다면,

1

0

0

-1

0

0

누적합을 한번 구하면

1

1

1

0

0

0

 이렇게 나오게 된다. 그럼 시작점 부터 끝점까지의 구간에 재생을 한 사람이 한명이라는 것이 된다.

 

누적합을 한 번 더 구하면

1

2

3

3

3

3

이렇게 시작점 부터 끝점까지의 구간에 재생을

한 시간이 3으로 저장되게 된다.

 

이렇게 구해진 누적재생시간을 이용하여

long time = play[i + advTime] - play[i];

위와 같이 0 부터 전체 재생시간까지의 구간에 누적재생시간이 가장 큰 구간을 구하면 된다.

 

이 외에도 문자를 숫자화 시키고 숫자를 시간처럼 표현하는 등의 메소드는 따로 설명하지 않겠다.

 

<전체시간>

import java.util.*;

class Solution {
    
    public String solution(String play_time, String adv_time, String[] logs) {
        String answer = "";

        if(play_time.equals(adv_time)){
            return "00:00:00";
        }      
        
        int playTime = timeToInt(play_time);
        int advTime = timeToInt(adv_time);
        long[] play = new long[playTime + 1];
        
        for(int i = 0 ; i < logs.length ; i++){
            int start = timeToInt(logs[i].substring(0, 8));
            int end = timeToInt(logs[i].substring(9, 17));
            
            play[start]++;
            play[end]--;
        } 
        
        // 누적 시청자수
        for(int i = 1 ; i <= playTime ; i++){
            play[i] += play[i - 1];
        }
        
        // 누적 재생시간
        for(int i = 1 ; i <= playTime ; i++){
            play[i] += play[i - 1];
        }
        
        long max = play[advTime - 1];
        int maxIndex = 0;
        for(int i = 0 ; i + advTime <= playTime ; i++){
            long time = play[i + advTime] - play[i];
            
            if(time > max){
                max = time;
                maxIndex = i + 1;
            }
        }
        
        answer = intToTime(maxIndex);
        return answer;
    }
    
    private static String intToTime(int time){
        
        int hour = time / 3600;
        time %= 3600;
        int minute = time / 60;
        int sec = time % 60;
        
        return String.format("%02d:%02d:%02d", hour, minute, sec);
    }
    
    private static int timeToInt(String time){
        int int_time = 0;
        String[] splitTime = time.split(":");
        
        for(int i = 0 ; i < 3 ; i++){
            int_time += (Math.pow(60, 2 - i) * parseInt(splitTime[i]));
        }
        
        return int_time;
    }
    
    private static int parseInt(String string){
        return Integer.parseInt(string);
    }
}