22.06.11. 풀었던 문제들

1. 광고 삽입

처음 접근은 two-pointer로 풀려 했는데, two-pointer로 풀 경우 right index가 한 칸 넘어갔을 때 right index보다 작은 모든 값들에 대해 계산을 다시 해 주어야 했다 - two-pointer지만 시간복잡도에서 이득보지 못하기 때문에 pass

다음 접근은 사용자가 보기 시작하는 시간에 +1, 다 본 시간에 -1을 하고 그 구간을 저장하고, 이 구간을 이용해 풀려 했는데 위와 같은 이유로 pass

잘 모르겠어서 다른 블로그들 참고(답을 봤다)했더니 바로 위 접근에서 조금만 변경하면 되었다. 아쉽다... 방법은 모든 시간에 대해 사용자가 보는 경우 +1, 안 보는 경우 -1을 2번 누적합을 만들고 i~j까지 부분합을 이용해 풀 수 있는 문제였다. 다만 누적합을 만들 때, 모든 사용자들의 시작시간~끝시간에 대해 +1을 해 버리면 360000*300000이므로 시간 초과가 날 수도 있다. 따라서 조금의 최적화가 필요하다.

또는 슬라이딩 윈도우로 풀 수도 있다. 모든 시간에 사용자가 보는 경우 +1, 안 보는 경우 -1을 해서 sliding window 내부의 값을 구하고, 한 칸씩 오른쪽으로 움직여 값을 구하는 방법이다.

주의점. long long으로 써야 한다. 최대 36만 칸에 30만 사용자가 보기 떄문에 크기가 20억을 넘기 때문.

// 광고 삽입

#include <string>
#include <algorithm>
#include <vector>
#include <iostream>

using namespace std;

string secondToString(int s){
    int h = s / 3600; s %= 3600;
    int m = s / 60; s %= 60;
    
    string sh = to_string(h);
    if(h<10){
        sh = "0" + sh;
    }
    string sm = to_string(m);
    if(m < 10){
        sm = "0" + sm;
    }
    string ss = to_string(s);
    if(s < 10){
        ss = "0" + ss;
    }
    return sh + ":" + sm + ":" + ss;
}

int stringToSecond(string s){
    int h = stoi(s.substr(0, 2));
    int m = stoi(s.substr(3, 2));
    int ss = stoi(s.substr(6, 2));
    return 3600 * h + 60 * m + ss;
}

string solution(string play_time, string adv_time, vector<string> logs) {
    int num_logs = logs.size();
    int splay_time = stringToSecond(play_time), sadv_time = stringToSecond(adv_time);
    vector<int> viewers(splay_time+1, 0);
    for(string s : logs){
        viewers[stringToSecond(s.substr(0, 8))]++;
        viewers[stringToSecond(s.substr(9, 8))]--;
    }
    
    // viewers[i] : i시간에 보는 사람들 수
    for(int i = 1; i<splay_time+1; i++){
        viewers[i] += viewers[i-1];
    }
    
    long long max_adv_time = 0, window_sum = 0;
    string answer = "";
    for(int i = 0; i<sadv_time; i++){
        window_sum += viewers[i];
        answer = secondToString(0);
    }
    max_adv_time = window_sum;
    
    
    for(int i = sadv_time; i<splay_time+1; i++){
        window_sum += (viewers[i] - viewers[i-sadv_time]);
        if(max_adv_time < window_sum){
            answer = secondToString(i - sadv_time + 1);
            max_adv_time = window_sum;
        }
    }
    
    return answer;
}

 

2. 외벽 점검

입력 size가 작기 때문에 brute-force로 풀어도 될까? 생각해 본다. 먼저 8! = 4만, weak의 모든 지점을 시작지점으로 두고 시계 / 반시계로 각각 돌면 15 * 2. 다만 여기서, 시계방향으로 탐색 경우의 수 == 반시계방향으로 탐색하는 경우의 수이다. 왜냐하면 반시계방향은 가는 방향이 반시계인 것이기 때문에, 1->10으로 탐색했다고 하면 10->1로 탐색하는 것과 동일하기 때문이다. 따라서 한 방향만 탐색해도 된다.

그러면 weak의 모든 지점을 circular로 돌려가면서 돌리면 15 * 4만. 그리고 friend 조합으로 weak 탐색 가불 여부는 15 * 8에 가능. 그러면 1억 내로 해결 가능하다! 브루트 포스로 가자.

실수한 부분은, 현 위치부터 탐색 가능한 widx를 구하는 것에서 실수했다.

나는 clockwise라는 배열을 두고 매번 계산해 주었는데 이럴 필요 없이 기존 배열 크기를 2로 늘리고 weak.size()부터 end까지 n을 더해주는 방법도 있다.

 

// 외벽 점검

#include <string>
#include <vector>
#include <deque>
#include <algorithm>

using namespace std;

int INF = 99999;

int solution(int n, vector<int> weak, vector<int> dist) {
    deque<int> weaks(weak.begin(), weak.end());
    sort(dist.begin(), dist.end());
    
    int weaksize = weak.size(), distsize = dist.size();
    
    weaks.push_front(weaks.back()); weaks.pop_back();
    int answer = INF;
    for(int cycle_num = 0; cycle_num<weaksize; cycle_num++){
        weaks.push_back(weaks.front()); weaks.pop_front();

        vector<int> clockwise(weaks.begin(), weaks.end());        
        
        int clockwise_min = clockwise[0];
        for(int i = 0; i<weaksize; i++){
            clockwise[i] -= clockwise_min;
            if(clockwise[i] < 0) clockwise[i] += n;
        } // 시계방향. 제일 첫 지점은 무조건 0으로 두고, 값이 음수면 n 더해주자.
        
        do{
            int friend_num = 0, widx;
            // 현 조합으로 모든 weak 탐색 가불 조사
            for(widx = 0; widx < weaksize; widx++){
                friend_num++;
                if(friend_num > dist.size()){
                    // 만약 friend 수가 너무 크면 불가. false
                    friend_num = 0;
                    break;
                }
                // 현 위치, 현 탐색중인 친구 index를 이용해 어디까지 탐색 가능한지 저장.
                int cur_position = clockwise[widx], cur_range = clockwise[widx] + dist[friend_num-1];
                // 다음 weak 지점이 탐색 가능 -> widx++
                while(widx + 1< weaksize){
                    if(clockwise[widx+1] <= cur_range) widx++;
                    else break;
                }
            }
            // 탐색 불가면 처음부터 다시.
            if(friend_num == 0) continue;
            // 가능하다면 min값 저장
            answer = min(answer, friend_num);
        }while(next_permutation(dist.begin(), dist.end()));   
    }
    
    return answer == INF? -1 : answer;
}
​