[2021 KAKAO BLIND RECRUITMENT] 광고 삽입

12875 단어 algorithmalgorithm

2021 KAKAO BLIND RECRUITMENT 광고 삽입

유형

  • 투포인터
  • 구간합

문제 풀이에 대한 감을 잡기 위해, 카카오 공식 문제 해설을 먼저 참고하였다. 시간 초과가 나지 않기 위해 투포인터를 사용해야 하는 문제였다.

코드

import java.util.stream.IntStream;

class Solution {

    public String solution(String play_time, String adv_time, String[] logs) {
        int play = getSecond(play_time);
        int adv = getSecond(adv_time);

        if(play == adv) return "00:00:00";
        int[] count = new int[60 * 60 * 100];

        for(String log : logs) {
            String[] str = log.split("-");
            int logStart = getSecond(str[0]);
            int logEnd = getSecond(str[1]);
            for(int i = logStart; i < logEnd; i++) {
                count[i]++;
            }
        }

        long sum = 0, max = 0, bestAdInsertTime = 0;

        for(int i = 0; i < adv; i++) {
            sum += count[i];
        }
        max = sum;

        for(int i = adv; i < play; i++) {
            sum += count[i];
            sum -= count[i - adv];
            if(sum > max) {
                max = sum;
                bestAdInsertTime = i - adv + 1;
            }
        }

        return getString(bestAdInsertTime);
    }

    private static int getSecond(String time) {
        String[] str = time.split(":");
        int second = Integer.parseInt(str[2]) + Integer.parseInt(str[1]) * 60 + Integer.parseInt(str[0]) * 3600;
        return second;
    }

    private static String getString(long second) {
        long hour = second / 3600;
        long min = second / 60 - hour * 60;
        long sec = second % 60;

        String s = String.format("%02d", hour) + ":" + String.format("%02d", min) + ":" + String.format("%02d", sec);
        return s;
    }
}

참고: https://yjyoon-dev.github.io/kakao/2021/01/29/kakao-insertad/

좋은 웹페이지 즐겨찾기