[Programmers] 2021 카카오 블라인드 채용 5번 - 광고 삽입

동영상이 play_time 만큼 재생된다.

시청자들의 시청 기록이 logs 배열로 주어진다. ("H1:M1:S1-H2:M2:S2")

시청자들의 누적 시간이 가장 길도록, 해당 영상에 adv_time 만큼의 광고를 넣고자 한다.

광고를 넣어야 하는 시점을 묻는 문제이다.

 

[조건]

- 1 <= logs 배열의 길이 <= 300,000

- 00:00:01 <= 동영상 및 공익광고 재생 시간<= 99:59:59

 

[풀이 과정]

 

예시 1

문제에 삽입된 위의 그림을 보면, Greedy 알고리즘의 대표적인 문제인 '수업 시간표 짜기' 문제가 떠오른다.

주어진 시간 내에 여러 수업이 있을 때, 가장 긴 시간 동안 수업을 듣는 경우의 수를 구하는 문제인데, 그 문제는 수업이 끝나는 시점을 기준으로 정렬한 뒤, Greedy하게 추가하는 것이 정답이다.

 

1) 시작 시각 or 종료 시각을 기준으로 정렬하기 (X)

정렬을 해서 문제를 어떻게 풀 수 있을지 고민하였다.

그러나, 시작 시각으로 정렬하거나, 종료 시각으로 정렬하더라도,
특정 시각의 시청자 수를 구하기 위해서는 logs의 모든 시청자를 살펴야 한다. 

 

정렬엔 큰 의미가 없었고, 완전 탐색으로 진행할 경우 아래와 같은 시간 복잡도를 갖는다.

시간 복잡도 = Time_play * (Time_play - 1) * (Time_adv) * Len (logs)
0 < Time_Play, Time_adv < 360,000 (100시간을 초로 변환)
0 < Len(logs) < 300,000

계산하면 대충 잡아도 10의 20승이 넘어간다.

정렬을 활용하는 방법은 포기.

 

2) 세그먼트 트리 (X)

구간 합을 구하는 방법으로 세그먼트 트리 자료형을 사용하곤 한다.

세그먼트 트리 자료형을 만들어두게 되면, 시각 t1부터 t2 사이의 시청자 수를 O (log N)으로 구할 수 있다.

세그먼트 트리 구현에는 O (T log T)의 시간이 소요되고, 여전히 광고의 시작과 끝점을 고르는데 O (T^2)의 시간이 필요하다.

 

3) 이분 탐색 (X)

보통 이렇게 자료가 많고, 경우의 수를 찾기 어려운 경우 이분 탐색으로 해결하기도 한다.

주어진 logs 데이터 또한 정렬을 할 수 있기 때문에, 이분 탐색을 써야하나? 싶었다.

그러나, time의 index 위에서 left와 right를 변경하는 기준을 찾을 수 없다.

따라서 이분 탐색도 말이 되지 않는다.

 

4) Memoization (O)

어떤 시청자가 들어왔고, 어떤 시청자가 나갔는지 몰라도 된다.

단순히 특정 시점 (HH:MM:SS) 때, 접속해있는 시청자의 수가 중요한 것이다.

 

따라서, logs 데이터를 훑으면서, 시청자가 들어왔을 때는 +1을, 나갔을 때는 -1을 해준다면,

특정 시점에 접속해있는 시청자의 수를 알 수 있을 것이다.

 

한 발 더 나아가서, 동영상 시작 시간으로부터 누적 시청자 수를 구해둔다면, 광고를 재생해야하는 시간 동안의 누적 시청 시간을 구할 수 있을 것이다. 이 방식을 사용한다면, O(total_time) 이나 O(length of Logs) 의 시간으로 해당 문제를 해결할 수 있다.

 

public class Programmers_kakao2021_5 {
	static int totalLength;                 // 총 영상 Play 길이
	static int check[];                     // [n] : n초에 추가되고, 나간 시청자 변동 
	static long sumFromZero[];              // sumFromZero[n] : 0초부터 n초까지 누적 재생 시간의 합 
	static int[] secsTable = {3600, 60, 1}; // 시, 분, 초당 몇 초인지

	static String secsToTime(int sec) { // 초를 HH:MM:SS로 바꿔주는 함수, String.format을 잘 활용하면 필요 없는 함수
		StringBuilder sb = new StringBuilder();
		
		for (int i = 0; i < 3; ++i) {
			if (sec / secsTable[i] < 10) {
				sb.append("0");
			}
			sb.append(sec/secsTable[i]);
			
			sec %= secsTable[i];
			
			if (i != 2)
				sb.append(":");
		}
		
		return sb.toString();
	}	
	static int timeToSecs(String[] parsedTime) { // HH:MM:SS를 초로 바꿔주는 함수
		int ret = 0;
		
		for (int i = 0; i < 3; ++i) {
			ret += Integer.parseInt(parsedTime[i]) * secsTable[i];
		}
		
		return ret;
	}
	
	public static String solution(String play_time, String adv_time, String[] logs) {
		int answer = 0;
		long maxTime = 0;
		int curWatcher = 0;
		int advTime = 0;
		
		totalLength = timeToSecs(play_time.split(":"));
		advTime = timeToSecs(adv_time.split(":"));
		check = new int[totalLength + 1];
		sumFromZero = new long[totalLength + 1];
		
		// checking start & end point of each logs
		for (int i = 0; i < logs.length; ++i) {
			String startTimeString = logs[i].split("-")[0];
			String endTimeString = logs[i].split("-")[1];
			
			int startTime = timeToSecs(startTimeString.split(":"));
			int endTime = timeToSecs(endTimeString.split(":"));
			
			check[startTime]++;
			check[endTime]--;
		}
		
		// Finding maxValue along the play_time
		curWatcher = check[0];
		sumFromZero[0] = 0;
		
		for (int i = 1; i <= totalLength; ++i) {			
			sumFromZero[i] = (sumFromZero[i - 1] + curWatcher);
			curWatcher += check[i];
			
			if (i - advTime >= 0) {
				if (maxTime < sumFromZero[i] - sumFromZero[i - advTime]) {
					maxTime = sumFromZero[i] - sumFromZero[i - advTime];
					answer = i - advTime;
				}
			}
		}
		
		return secsToTime(answer);
	}
	
	public static void main(String[] args) {
		System.out.println(solution("02:03:55", "00:14:15",
				new String[] {"01:20:15-01:45:14", "00:40:31-01:00:00", "00:25:50-00:48:29", "01:30:59-01:53:29", "01:37:44-02:02:30"}));
	}
}

 

 

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

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