[프로그래머스] 2021 KAKAO BLIND RECRUITMENT - "광고 삽입" (Java)

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

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

광고 삽입

 

---

 

난이도  : Level 3 

 

 슬라이딩 윈도우 알고리즘을 활용하여 문제를 해결하였습니다. 이 문제는 의도하는 로직을 떠올리는 것이 관건이라고 생각합니다. String으로 주어진 시간 정보를 초 단위로 환산하는 것은 간단할 수 있지만 이들을 활용하여 탐색을 하는 과정은 고민이 필요한 문제라고 생각합니다. 

 

 저는 아래와 같은 로직을 세워 문제를 풀었습니다.

1. String으로 주어진 시간 정보를 초 단위로 환산할 것.

2. 초 단위로 환산된 logs 배열의 정보를 기준으로 시청자 수를 누적할 것. 

3. 시청자 수를 누적하는 배열을 만들 것.( 최대 시간을 기준으로 배열의 크기를 잡습니다. 99:59:59 -> 359,999 ) 즉, 360,000을 배열의 크기로 잡습니다. 

4. 슬라이딩 윈도우를 사용하여 누적 시청자 수가 가장 큰 구간을 구할 것. ( 윈도우 사이즈는 전체 광고 길이입니다. )

5. 누적 시청자 수가 가장 큰 구간의 시작 시간을 String 값으로 변환하여 답을 출력.

 

 

 

- static int total_sec [] = new int[360000];

 누적 시청자 수를 저장하는 배열입니다. 초 단위로 저장될 수 있도록 배열의 크기를 최대 시간의 초(360,000)로 지정했습니다. 

 

 

 

- String solution(String play_time, String adv_time, String [] logs)

 동영상 재생 길이를 나타내는 play_time, 광고 재생시간 길이를 나타내는 adv_time, 시청자들이 해당 동영상을 재생했던 구간 정보를 담고 있는 logs 배열을 파라미터로 받습니다. StringToSec 함수를 통해 logs 배열의 구간 정보를 초 단위로 변환합니다. 그리고 구한 정보를 바탕으로 총구간을 저장하고 있는 total_sec 배열에 시청자 수를 누적 저장합니다. 여기서 주의할 점은 끝 시간 정보는 동영상을 끝내는 시간이기에 끝 시간 정보를 갖고 있는 index에는 시청자 수를 누적하지 않습니다.  

 

 동영상 재상 길이와 광고 재생 길이를 초 단위로 변환해주고, 광고 재생 길이를 윈도우 사이즈로 지정합니다. 슬라이딩 윈도우 알고리즘은 자료구조 큐를 활용하여 구현하였습니다. 0번째 인덱스부터 윈도우 크기만큼 초기 누적 시청자 수를 구해주고, 동영상 재생 길이까지 모든 구간을 탐색하며 최대 누적 시청자 수(max) 값을 비교합니다. max값이 변경되는 시점의 시작 지점을 따로 저장합니다. 

 

 마지막으로 max 값을 구하기 위하여 구한 시작 지점은 초 단위로 저장되어 있기 때문에, SecToString 함수를 통하여 String으로 변환하여 답을 반환합니다. 

 

 

 

- int StringToSec(String time)

 String 값으로 들어온 시간 정보를 초 단위로 환산하는 함수입니다. 

 

 

 

- String SecToString (int sec)

 초 단위로 들어온 시간 정보를 String 값으로 변환하는 함수입니다. 시, 분, 초 값이 각각 10보다 작을 경우는 앞에 "0"을 더해주고 반환하도록 하였습니다. 

 

 

  코드

import java.util.LinkedList;
import java.util.Queue;

class PM_72414 {
	// PM / 72414번 / 광고 삽입 / 구현, 슬라이딩 윈도우  / Level3 / 2021 KAKAO BLIND
	static int total_sec [] = new int[360000];
	public String solution(String play_time, String adv_time, String[] logs) {
		String answer = "";
		
		for(int i=0; i< logs.length; i++) {
			int log_start = StringToSec(logs[i].substring(0,8));
			int log_end = StringToSec(logs[i].substring(9,17));
			
			// 총 시청자 수 누적, 끝 시간 정보를 갖는 index는 누적하지 않는다.
			for(int s=log_start; s<log_end; s++) {
				total_sec[s]++;
			}
		}
		
		int play_time_sec = StringToSec(play_time); // 전체 재생 길이
		int adv_time_sec = StringToSec(adv_time); // 전체 광고 길이
		
		
		int answer_start_sec = 0;
		long sum_viewer = 0;
		Queue<Integer> sum_viewer_q = new LinkedList<>();
		// 큐를 이용한 슬라이딩 윈도우 
		for(int i=0; i<adv_time_sec; i++) {
			sum_viewer += total_sec[i];
			sum_viewer_q.add(total_sec[i]);
		}
		
		long max = sum_viewer;
		
		for(int i=adv_time_sec; i<=play_time_sec; i++) {
			sum_viewer += total_sec[i];
			sum_viewer_q.add(total_sec[i]);
			sum_viewer -= sum_viewer_q.poll();
			
			if(sum_viewer > max) {
				answer_start_sec = i - adv_time_sec + 1;
				max = sum_viewer;
			}
		}
		answer = SecToString(answer_start_sec);
	
        return answer;
    }
	
	public int StringToSec(String time) {
			
		String time_array[] = time.split(":");
		int hourToSec = Integer.parseInt(time_array[0]) * 60 * 60;
		int minToSec = Integer.parseInt(time_array[1]) * 60;
		int Sec = Integer.parseInt(time_array[2]);
		
		return hourToSec + minToSec + Sec;
	}
	
	public String SecToString (int sec) {
		
		String hourToString = Integer.toString(sec / 3600);
		sec %= 3600;
		String minToString = Integer.toString(sec / 60);
		sec %= 60;
		String secToString = Integer.toString(sec);
		
		if(Integer.parseInt(hourToString) < 10) hourToString = "0"+hourToString;
		if(Integer.parseInt(minToString) < 10) minToString = "0"+minToString;
		if(Integer.parseInt(secToString) < 10) secToString = "0"+secToString;
		return hourToString+":"+minToString+":"+secToString;
	}
}

 

피드백 환영합니다.