[프로그래머스] kakao 2021년 블라인드 (광고삽입) [JAVA]

문제링크 : programmers.co.kr/learn/courses/30/lessons/72414

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

카카오 블라인드 문제를 오랜만에 풀어보았다.

어느 시간에 공익광고를 넣는 것이 많은사람들이 보겠는가 하는 단순한 문제이다.

문자열로 주어지는 시간을 초 단위로 바꾸어서 배열에 저장하고 풀었다. => 100:00:00은 36만초이다. => 배열 크기 36만

광고를 넣을 수 있는 시간이 adv_play이며 간격이 일정하므로 투포인터를 떠올리기 쉽다.

투포인터 개념으로 최적의 광고시간을 구해주었다.

하지만 투포인터를 사용하기 위해서 전처리가 필요했는데

세그먼트 트리를 사용하였다.

 

★ 다른 사람의 풀이의 대부분은 전처리를 위해 log의 시작시간~ 끝 시간까지 반복문을 통해 배열을 갱신 해주었다.

=> 최악의 경우 모든 로그 데이터가 0시 ~ play_time 까지로 주어진 경우 30만 * 36만으로 시간초과가 난다고 판단했다

=> 효율성 점수가 없는 문제라서 유사 케이스가 없는 것 같은데 문제가 있어보인다. 처음부터 어려운 방식을 생각한 사람과 아닌 사람의 결과가 달라질 수 있다 생각한다.

 

어쨌든 세그먼트 트리로 log데이터의 start ~ end에 대해서 lazypropagation으로 업데이트 해준 후 

투포인터로 해결하였다. 

 

(참고) 문자열 포맷팅은 코드가 간결하지 못하다.

import java.io.*;
import java.util.*;
class Solution {
    public static long tree[];
	public static int reafSize;
	public static int StringToInt(String str){
		String hour = str.substring(0, 2);
		String minute = str.substring(3,5);
		String second = str.substring(6,8);
		return Integer.parseInt(hour) * 3600 + Integer.parseInt(minute) * 60 + Integer.parseInt(second);
	}
	public static void update(int start,int end){
		start += reafSize;
		end += reafSize;
		
		while(start<=end){
			if(start%2==1){
				tree[start++]+=1;
			}
			if(end%2==0){
				tree[end--] +=1;
			}
			start/=2;
			end/=2;
		}
	}
	public static void lazy(int cNode,long num){
		if(cNode >= reafSize*2) return;
		
		tree[cNode] += num;
		lazy(cNode*2,tree[cNode]);
		lazy(cNode*2+1,tree[cNode]);
	}
	
	public static String IntToString(int n){
		StringBuilder sb=  new StringBuilder();
		int hour = n/3600;
		int minute = n%3600/60;
		int second = n % (3600) % 60;
		if(hour/10 == 0){
			sb.append("0" + hour + ":"); 
		}else{
			sb.append(hour + ":");
		}
		if(minute/10 ==0){
			sb.append("0" + minute + ":");
		}else{
			sb.append(minute + ":");
		}
		if(second/10 == 0){
			sb.append("0" + second);
		}else{
			sb.append(second);
		}
		
		return sb.toString();
	}
	public static String solution(String play_time, String adv_time, String[] logs) {
        String answer = "";
        
        reafSize = 1;
        while(reafSize < 360000){
        	reafSize *=2;
        }
        tree = new long[reafSize*2];
        for(int i=0;i<logs.length;i++){
        	int s = StringToInt(logs[i].substring(0, 8));
        	int e = StringToInt(logs[i].substring(9));
        	update(s,e-1); //lazy update
        }
        
        //리프노드를 가지고 투포인터를 하기 위함
        lazy(1,0); 

        int gab = StringToInt(adv_time);
        int start = gab;
        int end = StringToInt(play_time);
        long candiCnt = 0;
        long ansCnt =0;
        int ans = 0;
        for(int i=0;i<gab;i++){
        	candiCnt += tree[i+reafSize];
        }
        ansCnt = candiCnt;
        
        while(start<=end){
        	candiCnt -= tree[start-gab+reafSize];
        	candiCnt += tree[start+reafSize];
        	
        	if(candiCnt >ansCnt){
        		ansCnt = candiCnt;
        		ans = start-gab + 1;
        	}
        	start+=1;
        }
        
        answer = IntToString(ans);
        return answer;
    }
}