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

광고 삽입(Lv3)

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

프로그래머스

 

 

 

 

풀이

이번 문제는 누적합을 이용해 풀었다.
먼저 string으로 주어진 시간들을 int로 변환했다. 이후 모든 logs에 대해 시작 시간에는 +1을 해주고, 끝나는 시간에는 -1을 해주었다.

for(int i=0; i<logs.length; i++){
	String[] log = logs[i].split("-");
	suffix[makeTime(log[0])]++;
	suffix[makeTime(log[1])]--;
}

 

다음으로 dp 배열을 생성해서 누적합을 계산하고, 광고 시간만큼을 먼저 계산해 초기값을 설정해줬다.

// 누적합 dp 계산
long[] dp = new long[suffix.length];
int startTime = 0;
dp[0] = suffix[0];
for(int i=1; i<dp.length; i++){
	dp[i] = suffix[i]+dp[i-1];
}
        
// 초기 계산
long compareMax = 0;
for(int i=0; i<advTime; i++){
	compareMax+=dp[i];
}
long maxTime = compareMax;

 

마지막으로 초를 하나씩 늘려가며 전체 경우에 대해 계산해줬다.

for(int i=advTime; i<dp.length; i++){
	compareMax-=dp[i-advTime];
	compareMax+=dp[i];
	if(compareMax>maxTime){
		maxTime = compareMax;
		startTime = i-advTime+1;
    }
}

 

 

전체 Code

class Solution {
    int playTime;
    int advTime;
    long[] suffix;
    public String solution(String play_time, String adv_time, String[] logs) {
    
    	// 시간 변환
        int time = makeTime(play_time);
        int advTime = makeTime(adv_time);
        
        // 누적합 생성
        suffix = new long[time+1];
        for(int i=0; i<logs.length; i++){
            String[] log = logs[i].split("-");
            suffix[makeTime(log[0])]++;
            suffix[makeTime(log[1])]--;
        }
        
		// 누적합 dp 계산
        long[] dp = new long[suffix.length];
        int startTime = 0;
        dp[0] = suffix[0];
        for(int i=1; i<dp.length; i++){
            dp[i] = suffix[i]+dp[i-1];
        }
        
        // 초기 계산
        long compareMax = 0;
        for(int i=0; i<advTime; i++){
            compareMax+=dp[i];
        }
        long maxTime = compareMax;
        
        // 하나씩 늘려가며 계산
        for(int i=advTime; i<dp.length; i++){
            compareMax-=dp[i-advTime];
            compareMax+=dp[i];
            if(compareMax>maxTime){
                maxTime = compareMax;
                startTime = i-advTime+1;
            }
        }
        
        int h = startTime/3600;
        int m = (startTime%3600)/60;
        int s = startTime%60;
        
        return String.format("%02d:%02d:%02d", h, m, s);
    }
    
    private int makeTime(String s){
        String[] arr = s.split(":");
        return transfer(arr[0])*3600+transfer(arr[1])*60+transfer(arr[2]);
    }
    
    private int transfer(String str){
        return Integer.parseInt(str);
    }
}