슬라이딩 윈도우 [프로그래머스] 광고 삽입

그림처럼 특정 영상(파란줄)이 주어지고 PIP 영상(검정줄)이 주어질 때 광고영상(빨간줄)을 어디 삽입해야 가장 영상들에 많이 겹칠 수 있는지를 푸는 문제였다.

사실 개념은 굉장히 간단한 편인데
문자열로 <-> 시간 간의 변환,
시간을 배열로 저장하는것,
문제를 슬라이딩 윈도우로 푸는 것을 떠올리기
의 3가지가 수반되어야 풀 수 있는 문제였다.

📌 초기 아이디어 (가능한 경우를 모두 완전탐색 + 백트래킹)

처음 아이디어는 모든 검정줄의 시작값, 끝값들을 저장해서, 빨간줄의 시작점이 검정줄들의 시작점이거나, 빨간줄들의 끝지점이 검정줄들의 끝점이라고 생각하여 이중 for문으로 구성했었는데,
검정줄 데이터가 최대 30만개이므로 30만 X 30만개의 연산을 처리해야 되는 경우에는 시간안에 절대 할 수 없었다.

모든 가능 시작점들을 저장하여 배열을 도는 for 문

for (int i = 0; i < startTime.length; i++) {
			int dupTime = 0;
			for (int j = 0; j < logs.length; j++) {
				int start = startTime[i];
				int end = startTime[i] + timeConverter(adv_time);
				int start2 = edgeTime[j].start;
				int end2 = edgeTime[j].end;
				if(end<=start2 || end2<=start)
					continue;
				dupTime += dupTimeCal(start, end, start2, end2);
			}
			if (dupTime > ans) {
				ans = dupTime;
				startAns = startTime[i];
				ansIdx = i;
			}
		}

그래도 이런 아이디어는 나쁘지 않았다고도 생각한다,,,

결론적으로는 슬라이딩 윈도우로 전체 영상 배열을 한번만 돌아서 답을 도출해야 했다!

📌 풀이

문자열을 시간으로 바꾸는 timeConverter

public static int timeConverter(String str) {
		int hour = Integer.parseInt(str.substring(0, 2)) * 3600;
		int min = Integer.parseInt(str.substring(3, 5)) * 60;
		int sec = Integer.parseInt(str.substring(6, 8));
		return hour + min + sec;
	}

시간을 문자열로 바꾸는 timeToStr

	public static String timeToStr(int time) {
		int hour = time / 3600;
		int min = (time - hour * 3600) / 60;
		int sec = time - hour * 3600 - min * 60;
		String hourString = Integer.toString(hour);
		String minString = Integer.toString(min);
		String secString = Integer.toString(sec);
		if (Integer.toString(hour).length() == 1)
			hourString = "0" + hourString;
		if (Integer.toString(min).length() == 1)
			minString = "0" + minString;
		if (Integer.toString(sec).length() == 1)
			secString = "0" + secString;

		return hourString + ":" + minString + ":" + secString;

	}

위 함수를 만들고 먼저 영상의 시작과 끝을 담는 배열을 만든다

int[] timeArr = new int[timeConverter(play_time) + 1];

그리고 각 PIP영상(검은 점)에 해당하는 시간들에 해당하는 인덱스에 ++을 해준다

for (int i = 0; i < logs.length; i++) {
			start = timeConverter(logs[i].substring(0, 8));
			end = timeConverter(logs[i].substring(9));
			for (int j = start; j < end; j++) {
				timeArr[j]++;
			}
		}

영상의 끝 값은 무시한다

중요한 점은 처음에는 for 문 안에 end도 포함시켰었는데, 영상이 0,8 이렇게 주어지면 0초부터 시작하여 8초까지 재생된다는 의미이므로 인덱스 0이(0~1초 구간), 1이(1~2초 구간)이라고 생각했을 때 0~7까지의 인덱스에만 표시를 해야한다.

이 점 때문에 계속 틀리거나 시간초과가 났었다.

그 다음 인덱스 0~영상의 길이만큼 시작하는 의미로 초기 initSum을 계산해주고

for (int i = 0; i < timeConverter(adv_time); i++) {
			initSum += timeArr[i];
		}

아래와 같이 1~전체영상길이-공익광고영상길이 까지 루프를 돌며 슬라이딩 윈도우를 이동시킨다. (인덱스가 옮겨가며 빠지는 값 빼고, 추가되는 값 넣어줌)

maxSum = initSum;
		for (int i = 1; i <= timeArr.length - advTimeLen - 1; i++) {
			initSum = initSum - timeArr[i - 1] + timeArr[i + advTimeLen - 1];
			if (initSum > maxSum) {
				maxSum = initSum;
				timeAns = i;
			}
		}

📌 전체코드

import java.util.Arrays;

class Solution {

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

		int[] timeArr = new int[timeConverter(play_time) + 1];
		int start = 0;
		int end = 0;
		long initSum = 0;
		long maxSum = 0;
		int timeAns = 0;
		int advTimeLen = timeConverter(adv_time);

		for (int i = 0; i < logs.length; i++) {
			start = timeConverter(logs[i].substring(0, 8));
			end = timeConverter(logs[i].substring(9));
			for (int j = start; j < end; j++) {
				timeArr[j]++;
			}
		}

		for (int i = 0; i < timeConverter(adv_time); i++) {
			initSum += timeArr[i];
		}
		maxSum = initSum;
		for (int i = 1; i <= timeArr.length - advTimeLen - 1; i++) {
			initSum = initSum - timeArr[i - 1] + timeArr[i + advTimeLen - 1];
			if (initSum > maxSum) {
				maxSum = initSum;
				timeAns = i;
			}
		}

		answer = timeToStr(timeAns);
		return answer;
	}

	public static int timeConverter(String str) {
		int hour = Integer.parseInt(str.substring(0, 2)) * 3600;
		int min = Integer.parseInt(str.substring(3, 5)) * 60;
		int sec = Integer.parseInt(str.substring(6, 8));
		return hour + min + sec;
	}

	public static String timeToStr(int time) {
		int hour = time / 3600;
		int min = (time - hour * 3600) / 60;
		int sec = time - hour * 3600 - min * 60;
		String hourString = Integer.toString(hour);
		String minString = Integer.toString(min);
		String secString = Integer.toString(sec);
		if (Integer.toString(hour).length() == 1)
			hourString = "0" + hourString;
		if (Integer.toString(min).length() == 1)
			minString = "0" + minString;
		if (Integer.toString(sec).length() == 1)
			secString = "0" + secString;

		return hourString + ":" + minString + ":" + secString;

	}
}