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

이형걸·2025년 1월 9일

Prefix sum 누적합

Problem Solving

목록 보기

2/23

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

🗒️알고리즘 분류

#누적합 #prefix sum

📌기억해야 할 포인트

우선 기본적으로 누적합 문제인 것을 문제를 보고 파악했다.

하지만, 문제에서 주어진 구간(adv_time)이 다른 구간들(logs)의 각각의 길이와 크기가 딱 맞아떨어지지 않는 것을 보고 당황해서 나머지 풀이를 생각해내지 못했다.

결국은 advTime 만큼의 크기를 구하고 (Arrays.stream().sum()), 한칸씩 옮기면서 맨 앞의 칸은 빼주고(sum -= playTimes[i-advTime]), 맨 뒤의 칸은 더해주면서(sum += playTimes[i]) 최대값을 갱신해주면 된다.
- 이때, 반복문의 i 값은 광고시간의 끝나는 시각이기 때문에 우리가 답으로 구하려는 광고의 시작시간은 i-advTime+1 이 된다!
시간(시,분,초)를 문자열로 나타낼 때는 String.format() 함수를 활용하자!
- String.format("%02d:%02d:%02d", num/3600, (num%3600)/60, num%60);

📝풀이 코드(JAVA)

import java.util.*;

class Solution {
    public String solution(String play_time, String adv_time, String[] logs) {
        String answer = "";
        int totalPlayTime = timeToNum(play_time);
        int[] playTimes = new int[totalPlayTime+1];
                
        for (String log : logs) {
            String[] split = log.split("-");
            int startTime = timeToNum(split[0]);
            int endTime = timeToNum(split[1]);
            
            ++playTimes[startTime];
            --playTimes[endTime];
        }
        
        for (int i = 1; i < totalPlayTime; ++i) {
            playTimes[i] += playTimes[i-1];
        }
        
        int advTime = timeToNum(adv_time);
        long sum = Arrays.stream(playTimes, 0, advTime).sum();
        long maxSum = sum;
        int maxStartTime = 0;
        
        for (int i = advTime; i < totalPlayTime; ++i) {
            sum += playTimes[i];
            sum -= playTimes[i-advTime];
            
            if (sum > maxSum) {
                maxSum = sum;
                maxStartTime = i-advTime+1;
            }
        }
        
        return numToTime(maxStartTime);
    }
    
    private int timeToNum(String time) {
        String[] split = time.split(":");
        return (Integer.parseInt(split[0])*3600) + (Integer.parseInt(split[1])*60) + Integer.parseInt(split[2]);
    }
    
    private String numToTime(int num) {
        return String.format("%02d:%02d:%02d", num/3600, (num%3600)/60, num%60);
    }
}