2021 Kakao blind - 광고 삽입(시간 문자열 파싱, 구간합-슬라이딩 윈도우) c++, java 풀이

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

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

- 일단 이 문제 풀면서 sprintf 사용법을 배움. printf와 비슷한데 출력만 하는 printf와 달리 원하는 모양으로 포맷팅된 문자열 결과를 char배열에 저장할 수 있어서 편리하다.

- 0초~100분*3600초-1 범위의 int배열을 선언해서 해당 초의 동영상 재생 갯수를 모두 카운트해준다.

- 그런 뒤에 공익광고 시간 범위 내에 최대의 시청자수가 나오는지를 슬라이딩 윈도우로 체크해가면서 풀 수 있다. 
슬라이딩 윈도우 방식으로 풀지 않고 해당 범위를 모두 체크하게 되면 전체범위에서 해당 광고시간 범위를 또 읽게 되서 복잡도가 O(N^2)이 되는데 그렇게 되면 360000초^2가 되서 약 1200억의 실행시간이 걸리므로 전체 시간범위를 한번만 읽어도 되는 슬라이딩 윈도우 방식으로 풀 수 있다. 

- 구간합을 구할때 해당범위의 앞뒤 인덱스만 더하고 빼는 식으로 범위를 전진시켜나가는 방식으로 최적화 할 수 있음(구간의 범위가 정해져있는 슬라이딩 윈도우 방식)

#include <string>
#include <vector>
#include <iostream>
#include <sstream>
using namespace std;

int timeline[100 * 3600]; // timeline[i] = 같은 시간대 시청자수

// 누적 재생시간이 많이 나오는 공익광고 시간대 배치했을 때 시작시간, 가장빠른 시작시간
int changeInSeconds(string s) {
    stringstream ss(s); // 99:99:99
    int hour, min, sec;
    char etc;
    ss >> hour >> etc >> min >> etc >> sec;
    
    return hour * 3600 + min * 60 + sec;
}

string makeTimeStr(int n) { // 360000 -> 100:00:00    
    char s[9];
    sprintf(s, "%02d:%02d:%02d", n/3600, n/60 % 60, n%60);
    string str = s;
    return str;
}

string solution(string play_time, string adv_time, vector<string> logs) {
    int playTime = changeInSeconds(play_time); // 전체동영상 재생시간길이
    int advTime = changeInSeconds(adv_time); // 공익광고 재생시간 길이
    
    for(string log: logs) {
        int start = changeInSeconds(log.substr(0, 8)); // 99:99:99-99:99:99
        int end = changeInSeconds(log.substr(9,8));        
        for(int i = start; i< end; ++i) {
            ++timeline[i];
        }
    }
    
    // 360000^2 = 1200억, On^2 미만으로 풀어야
    // advtime = 종료시간 - 시작시간, 시작시간=종료시간-advtime, 종료시간=시작시간+advtime

    long long nowSum = 0;
    int startIdx = 0;
    for(int i = 0; i < advTime; ++i) { // 범위: 인덱스0 ~ advTime-1까지 
        nowSum += timeline[i];
    }
    long long maxSum = nowSum;
    
    for (int i = advTime; i < playTime; ++i) { // 끝나는 시간
        nowSum += timeline[i];
        nowSum -= timeline[i-advTime]; // 범위: 인덱스 1~advTime
        
        if(nowSum > maxSum) {
            maxSum = nowSum;
            startIdx = i - advTime + 1;
        }
    }
    
    return makeTimeStr(startIdx);
}

import java.util.*;

class Solution { // 4*3*3*3 = 108
    Map<String, Integer> parsed = new HashMap<>() {
        {
            put("-", 0);
            put("cpp", 1);
            put("java", 2);
            put("python", 3);
            put("backend", 1);
            put("frontend", 2);
            put("junior", 1);
            put("senior", 2);
            put("chicken", 1);
            put("pizza", 2);
        }
    };
    List<Integer>[][][][] a = new ArrayList[4][3][3][3];

    public int[] solution(String[] info, String[] query) { // 5만 + 10만
        int[] answer = new int[query.length];

        for (int i = 0; i < 4; ++i)
            for (int j = 0; j < 3; ++j)
                for (int k = 0; k < 3; ++k)
                    for (int l = 0; l < 3; ++l)
                        a[i][j][k][l] = new ArrayList<>();

        for (String s : info) {
            StringTokenizer st = new StringTokenizer(s);
            int lang, pos, exp, food, score;
            lang = parsed.get(st.nextToken());
            pos = parsed.get(st.nextToken());
            exp = parsed.get(st.nextToken());
            food = parsed.get(st.nextToken());
            score = Integer.parseInt(st.nextToken());

            for (int i = 0; i < (1 << 4); ++i) { // 0000 ~ 1111
                int[] p = { lang, pos, exp, food };
                for (int j = 0; j < 4; ++j) {
                    if ((i & (1 << j)) == 0)
                        p[j] = 0;
                }
                a[p[0]][p[1]][p[2]][p[3]].add(score);
            }
        }

        for (int i = 0; i < 4; ++i)
            for (int j = 0; j < 3; ++j)
                for (int k = 0; k < 3; ++k)
                    for (int l = 0; l < 3; ++l)
                        Collections.sort(a[i][j][k][l]);

        for (int i = 0; i < query.length; ++i) {
            StringTokenizer st = new StringTokenizer(query[i]);
            int lang, pos, exp, food, score;
            lang = parsed.get(st.nextToken());
            st.nextToken();
            pos = parsed.get(st.nextToken());
            st.nextToken();
            exp = parsed.get(st.nextToken());
            st.nextToken();
            food = parsed.get(st.nextToken());
            score = Integer.parseInt(st.nextToken());
            answer[i] = getNum(a[lang][pos][exp][food], score);
        }

        return answer;
    }

    int getNum(List<Integer> list, int score) {
        if (list.isEmpty())
            return 0;
        int s = 0, e = list.size();
        while (s < e) {
            int mid = s + (e - s) / 2;
            if (list.get(mid) >= score)
                e = mid;
            else
                s = mid + 1;
        }

        return list.size() - e;
    }
}