[프로그래머스] 2021 카카오/ 광고 삽입 (Java)

#5 광고 삽입

2021 카카오 블라인드

난이도 : LEVEL 3

유형 : 구간합 / 누적합 / 슬라이딩 윈도우

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

[문제]

"죠르디"의 동영상 재생시간 길이 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자리 문자열로 반환합니다.

 

문제 풀이

맨 처음 풀때는 String데이터를 그대로 다루려해서 많이 헤매었다. 무조건 int로 바꿔풀어야한다.

 

1. String 데이터를 int 데이터로 변환하기

String자체가 무겁기 때문에 성능 저하요소로 크게 작용한다. 그래서 구간합을 구할 때는 int형으로 변환해서 사용하고 다시 출력할 때는 String으로 변환해준다.

static int timeToInt(String time) {
		String[] times = time.split(":");
		int toSec = 3600;
		int totalTime = 0;
		for(String t : times) {
			int num = Integer.parseInt(t);
			totalTime += num*toSec;
			toSec /= 60;
		}
		return totalTime;
	}
	
static String timeToString(int time) {
		String t = "";
		int hour = time/3600;
		time %= 3600;
		if(hour <10) t+= "0"+ hour +":";
		else t += hour+":";
		
		int minute = time/60;
		time %= 60;
		if(minute <10) t+= "0"+ minute+":";
		else t += minute+":";
		
		int second = time;
		if(second <10) t+= "0"+ second;
		else t += second;
		
		return t;
	}

 

2. 공간 복잡도 고려하기

JVM은 최소 32MB 최대 256MB의 공간을 가지고 있다.

• 총 플레이 시간은 100시간으로 초로 환산하면 360,000초이다.
• 1초에 int 1개 영역을 차지하므로 4byte이다.
• 360,000 * 4bytes = 1,440,000 bytes ≈ 1.44MB으로 int 배열 할당에 충분한 크기이다.

 

3. 시간 복잡도 고려하기

이중 포문으로 하면 시간복잡도는 O(N*M)으로 시간초과가 발생한다.

• for i : 0~ play_len (36만) O(N)
  • for j: i ~ i+adv_len (36만) O(M)

→ 그래서 누적합과 슬라이딩 윈도우 방식을 사용해서 풀이를 해주면 된다.

 

구간합

logs(최대 30만; K)을 탐색하면서 ad 배열에 구간합을 저장해준다. 

 

시간복잡도 O(N*K)

→ 최악의 경우 30만*36만의 연산을 하게 되는데 해당 로직은 중요하지 않아 테스트케이스에 포함되어 있지 않은 것 같다.

for(String log : logs) {
	String[] l = log.split("-");
	int start = timeToInt(l[0]);
	int end =  timeToInt(l[1]);
	for(int i=start; i<end; i++) {
		ad[i]++;
	}
}

 

슬라이딩 윈도우

처음에 0~adv_len을 탐색해주어 초기값을 설정해준다.  그 다음 투 포인터를 사용하여  Queue의 작동방식과 같이 새롭게 들어오는 누적합(ad[i])는 더해주고 꼬리 지점에 있는 누적합(ad[i-adv_len])은 빼주면서 값을 비교하여 최대값을 찾아주면 된다.

 

이중포문의 시간복잡도O(N^2)를  시간 복잡도 O(N-M)으로 줄일 수 있다.

int max_idx=0;
long max_sum=0;
long sum =0;

// 초기값 
for(int i=0; i<adv_len; i++) {
	sum += ad[i];
}
max_sum = sum;

// 투 포인터
for(int i = adv_len; i<play_len; i++) {
	sum += ad[i] - ad[i-adv_len];
	if(sum > max_sum) {
		max_sum = sum;
		max_idx = i-adv_len+1;
	}
}

 

풀이 코드 

이번 문제 풀이로 느낀 점은 다음과 같다.

1. String data를 int로 다룰 수 있는지 생각하기
2. 공간 크기 제한, 이중 포문 시간 복잡도 고려
3. 문제의 본질부터 파악하기 (구간합, 누적합, 슬라이딩 윈도우)

class Solution {
    public String solution(String play_time, String adv_time, String[] logs) {
		int play_len = timeToInt(play_time);
		int adv_len = timeToInt(adv_time);
		
		int[] ad = new int[360_000];
		
		for(String log : logs) {
			String[] l = log.split("-");
			int start = timeToInt(l[0]);
			int end =  timeToInt(l[1]);
			for(int i=start; i<end; i++) {
				ad[i]++;
			}
		}
		
		int max_idx=0;
		long max_sum=0;
		long sum =0;
		for(int i=0; i<adv_len; i++) {
			sum += ad[i];
		}
		max_sum = sum;
		
		for(int i = adv_len; i<play_len; i++) {
			sum += ad[i] - ad[i-adv_len];
			if(sum > max_sum) {
				max_sum = sum;
				max_idx = i-adv_len+1;
			}
		}
		
		return timeToString(max_idx);

    }
  static int timeToInt(String time) {
		String[] times = time.split(":");
		int toSec = 3600;
		int totalTime = 0;
		for(String t : times) {
			int num = Integer.parseInt(t);
			totalTime += num*toSec;
			toSec /= 60;
		}
		return totalTime;
	}
	
	static String timeToString(int time) {
		String t = "";
		int hour = time/3600;
		time %= 3600;
		if(hour <10) t+= "0"+ hour +":";
		else t += hour+":";
		
		int minute = time/60;
		time %= 60;
		if(minute <10) t+= "0"+ minute+":";
		else t += minute+":";
		
		int second = time;
		if(second <10) t+= "0"+ second;
		else t += second;
		
		return t;
	}
}