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

1. 문제 링크
2. 카카오 해설집
3. 참고 블로그

1. 문제 해결

카카오는 시간과 관련된 문자열을 좋아한듯하다.
여튼, 카카오 문제를 풀다보면 시간과 관련된 문자열이 나오는데 시,분,초 각각 따로따로 진행하게 되면 문제를 해결하는데 어려워진다.

따라서, 반드시 초 단위 로 바꿔서 진행하는 게 좋다.

초 단위로 통일하는 것은 알겠으나 도통 방법이 떠오르지 않아서 카카오 해설집을 봤는데.. 카카오 해설집을 봐도 이해가 되지 않아 다른 블로그를 참고하였다. 설명이 정말 간결하게 되어있다.

참고하여 구성한 알고리즘은 다음과 같다.

1. 주어진 시간 문자열을 초 단위로 바꾼다.
2. info 배열을 이용하여 시작 시간과 끝 시간에 해당되는 구간의 시청자 수를 누적한다.
3. 0~광고 시간(adv_time)까지의 누적 시청자 수를 구한다.
4. 1~동영상 재생시간 길이(play_time)까지 누적 시청자가 가장 많으면서 빠른 시작 시간을 구한다.

주의해야 할 부분은 3~4번이다.

2. 소스 코드

import java.util.*;
class Solution {
   public static String solution(String play_time, String adv_time, String[] logs) {
		int[] time = new int[60 * 60 * 100];

		int play = convert(play_time);
		int adv = convert(adv_time);

		for (int i = 0; i < logs.length; i++) {
			int[] ct = convertTime(logs[i]);

			int logs_start = ct[0];
			int logs_end = ct[1];

			// 해당 구간의 시청자 수
			for (int j = logs_start; j < logs_end; j++)
				time[j]++;
		}

		long max = 0;
		long sum = 0;

		Queue<Integer> q = new LinkedList<>();
		for (int i = 0; i < adv; i++) {
			q.add(time[i]);
			sum += time[i];
		}
		max = sum;
		int start = 0;
		for (int i = adv; i < play; i++) {
			sum += time[i];
			q.add(time[i]);
			sum -= q.poll();

			if (max < sum) {
				max = sum;
				start = i - adv + 1;
			}
		}

		return convertSecToString(start);
	}

	private static String convertSecToString(int start) {
		String hour = String.format("%02d", start / 3600);
		String minute = String.format("%02d", (start % 3600) / 60);
		String sec = String.format("%02d", ((start % 3600) % 60));

		return hour + ":" + minute + ":" + sec;
	}

	private static int[] convertTime(String time) {
		String[] split = time.split("-");

		int[] ret = new int[2];
		for (int i = 0; i < 2; i++) {
			ret[i] = convert(split[i]);
		}

		return ret;
	}

	private static int convert(String time) {
		String[] split = time.split(":");
		int ret = 0;

		int[] t = { 3600, 60, 1 };
		for (int i = 0; i < split.length; i++) {
			ret += Integer.parseInt(split[i]) * t[i];
		}

		return ret;
	}
}