[프로그래머스(Programmers)][자바(java)] (Lv3) 광고 삽입

 

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

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

 

문제 요약

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

• play_time, adv_time은 HH:MM:SS 형식이며, 00:00:01 이상 99:59:59 이하
• logs 배열의 각 원소는 H1:M1:S1-H2:M2:S2 형식

1. 동영상 재생시간 = 재생이 종료된 시각 - 재생이 시작된 시각
   ( 예를 들어, 00시 00분 01초부터 00시 00분 10초까지 동영상이 재생되었다면, 동영상 재생시간은 9초 입니다 .) 

 

문제 풀이

*  문자열 파싱, 누적 합, 구현

-  입력받은 시간 형식의 문자열( String )을 초( int )로 바꾸는 함수 int convert_to_seconds() 작성
  ( 최대 초는 99*3600 + 59*60 + 59 = 359999 )

-  초( int )를 시간 형식의 문자열( String )으로 바꾸는 함수 String convert_to_time() 작성

-  입력 받은 재생시간 길이 play_time, 공익광고의 재생시간 길이 adv_time, 
   시청자들이 해당 동영상을 재생했던 구간 정보 logs 를 각각 초 단위로 변환  ( h*3600 + m*60 + s )
    -  String play_time  =>  int pt  // play_time : 재생 시간
    -  String adv_time  =>  int at  // adv_time : 광고 시간
    -  String logs[i].split("-")[0]  =>  int ls  // log_start : 로그의 재생 시작 시각
    -  String logs[i].split("-")[1]  =>  int le  // log_end : 로그의 재생 종료 시각

-  재생 시간( 0 ~ pt-1 초 ) 동안 시청자들이 동영상을 재생한 누적 시간을 구해야 함
   pt+1 크기의 ※ long vt[] ( viewing_time ) 배열 생성

-  우선 i 초( 0 <= i < pt ) 일 때의 재생 횟수를 구함.
   logs[]의 원소 개수( 배열의 크기 ) 만큼 루프를 돌며 ls ~ le-1 까지 vt[i]++ 함  ( ls <= i < le )
 ( 문제에서 '동영상 재생시간 = 재생이 종료된 시각 - 재생이 시작된 시각' 이라고 했으므로
   실질적인 재생 시간은 재생이 시작된 시각 ~ 재생이 종료된 시각-1 )

-  i 초일 때의 누적 재생 시간( 0 ~ i+1 초 간의 구간을 포함 )은 i-1 초의 재생 시간을 더한 값이 되므로
   루프를 돌며 이전 초의 재생 시간을 더해줌  ( vt[i] += vt[i-1] ) ( 1 <= i < pt )

-  s ~ e 초 동안 시청자들의 총 재생 시간( vt_c : viewing_time_cur )은 vt[e] - vt[s] 이다.
   재생 시간이 가장 긴 구간이 광고를 삽입하는 최적의 구간이므로,
   최적의( 그 중 가장 빠른 ) 광고 시작 시각( as_o : adv_start_optimal )을 구하기 위해
   lt_a[e] - lt_a[s] 가 가장 큰 구간( vt_m : viewing_time_max )을 찾아야 한다.

-  광고가 끝나는 시각( ae : adv_end )을 기준으로, 광고가 시작하는 시각( as : adv_start )은 ae - at 가 된다.
   vt_m의 초기값은 vt[at] - vt[0] 이다.

-  ae가 at+1 ~ pt-1 초 일 때 vt_c가 가장 큰 구간의 시작시간 as + 1이 as_o가 됨

import java.util.StringTokenizer;

public class Solution {
	
	public int convert_to_seconds( String time ) {
		StringTokenizer st = new StringTokenizer( time, ":" );
		return Integer.parseInt( st.nextToken() )*3600 + Integer.parseInt( st.nextToken() )*60 + Integer.parseInt( st.nextToken() );
	}
	
	public String convert_to_time( int seconds ) {	
		return String.format( "%02d:%02d:%02d", seconds/3600, (seconds/60)%60, seconds%60 );
	}
	
	public String solution(String play_time, String adv_time, String[] logs) {
		int pt = convert_to_seconds( play_time ), at = convert_to_seconds( adv_time );  // 최대 초는 359999 ( 99*3600+59*60+59 )
		if( pt == at )
			return convert_to_time( 0 );
		int ls, le, i;  // log_start/end
		long vt[] = new long[pt+1];  // viewing_time_accumulated
		StringTokenizer st;
		for( String l : logs ) {
			st = new StringTokenizer( l, "-" );
			ls = convert_to_seconds( st.nextToken() );
			le = convert_to_seconds( st.nextToken() );
			for( i = ls; i < le; i++ )  /* i ~ i+1 초 간의 구간을 포함하는 재생 구간 개수 */
				vt[i]++;
		}
		for( i = 1; i < pt; i++ )  /* 0 ~ i+1 초 간의 구간을 포함하는 누적 재생 시간 */
			vt[i] += vt[i-1];
		int as_o = 0, as, ae;  // adv_start_optimal, adv_start/end
		long vt_c, vt_m = vt[at];  // viewing_time_current, viewing_time_max
		for( i = at+1; i < pt; i++ ) {  // i => ae, i-at =>  as
			as = i-at;
			ae = i;
			vt_c = vt[ae] - vt[as];
			if( vt_m < vt_c ) {
				vt_m = vt_c;
				as_o = as+1;
			}
		}
        return convert_to_time( as_o );
    }
}