23.08.08. 풀었던 문제들 복기

BOJ 7512. 연속하는 소수의 합

 어떤 n1, n2, ... n$_m$이 주어졌을 때 연속된 n$_i$개의 소수의 합으로 나타낼 수 있는 가장 작은 소수를 찾는 문제. 처음에는 n개의 연속된 소수의 합을 빠르게 계산하기 위해 prefix sum을 사용했고, 메모리가 터졌다. 대체 왜..? 계산해 보면 그렇게 큰 값도 아닌데.

////////////////////// write your code below

// 1000000000000
int INF = 1e7+1;
//int INF = 312;
vector<int> primes;
vector<ll> psum;
void getPrime(){
    vector<bool> isPrime(INF+1, true);
    isPrime[0] = isPrime[1] = false;
    for(int i = 2; i<=sqrt(INF); i++){
        if(isPrime[i]){
            for(int j = i*i; j<=INF; j+=i){
                isPrime[j] = false;
            }
        }
    }

    for(int i = 2; i<INF; i++){
        if(isPrime[i]) primes.push_back(i);
    }

    //cout<<primes.size();
    psum.resize(primes.size());
    psum[0] = primes[0];
    for(int i = 1; i<primes.size(); i++){
        psum[i] = primes[i] + psum[i-1];
    }
    // cout<<psum[primes.size()-1]; // 3조정도가 max값
    // psum[i] - psum[j] = j+1부터 i까지 sum
}

int solve(){
	int m; cin>>m;
    vector<int> arr(m);
    for(int i = 0; i<m; i++) cin>>arr[i];
//    sort(arr.begin(), arr.end(), less<int>());

    map<ll, int> mapper;
    for(int l : arr){
        for(int i = 0; i<psum.size()-l; i++){
            if(i == 0) mapper[psum[i+l-1]]++;
            else mapper[psum[i+l-1] - psum[i-1]]++;
        }
    }
    


    for(auto const &p : mapper){
        if(p.second == m) return p.first;
    }

    /*
    for all m
        1. arr[0]으로 합친 게 소수인지 확인한다.
            - 소수이면 다른 arr[i]에 대해 같은 값인지 확인한다.
                - 같으면 계속.
                - 다르면 시작 index를 1 늘리고, 1번으로 감.

    */

    return 0;
}

 

 그래서 sliding window로 돌렸다. 결국 O(n)에 해결하는 건 같고, 추가 공간을 안 쓰니까.. 소수 계산하는 거야 소수 판정 알고리즘 포스팅에 작성한 에라토스테네스의 체로 O(nloglogn)으로 해결할 수 있다. n이 1천만 정도 되니까 얘는 문제가 안 되고.

 다음으로, 각 n$_i$에 대해 연속된 n$_i$개의 소수 합이 소수인지 + 소수이면 map에 넣고 count를 1 증가시켰다. 모든 n$_i$에 대해 이를 돌리고 map count가 m인 제일 작은 소수가 정답이므로 그것을 리턴. 이 때 연속된 n$_i$개의 합은 sliding window로 풀었다.

• 그러면 map[k]가 의미하는 것은 [연속된 n$_i$개의 소수 합으로 k를 나타낼 수 있는 i 개수]가 된다.

////////////////////// write your code below

// 1000000000000
int INF = 1e7+1;
//int INF = 312;
vector<bool> isPrime(INF+1, true);
vector<int> primes;
int psize;
//vector<ll> psum;
void getPrime(){
    isPrime[0] = isPrime[1] = false;
    for(int i = 2; i<=sqrt(INF); i++){
        if(isPrime[i]){
            for(int j = i*i; j<=INF; j+=i){
                isPrime[j] = false;
            }
        }
    }

    for(int i = 2; i<INF; i++){
        if(isPrime[i]) primes.push_back(i);
    }
    psize = primes.size();
}

int solve(){
	int m; cin>>m;
    vector<int> arr(m);
    for(int i = 0; i<m; i++) cin>>arr[i];

    int cnt = 0;
    map<int, int> mapper;
    for(int l : arr){
        // sliding window init
        int sum = 0;
        for(int i = 0; i<l; i++){
            sum += primes[i];
        }
        if(sum > INF) break;
        if(isPrime[sum] && (mapper[sum] == cnt || mapper[sum] == 0)) mapper[sum]++;

        // slide to the end
        for(int i = l; i<psize - l; i++){
            sum += primes[i] - primes[i-l];
            if(sum > INF) break;
            if(isPrime[sum] && (mapper[sum] == cnt || mapper[sum] == 0)) mapper[sum]++;
        }

        cnt++;
    }
    
    for(auto const &p : mapper){
        if(p.second == m) return p.first;
    }

    /*
    for all m
        1. arr[0]으로 합친 게 소수인지 확인한다.
            - 소수이면 다른 arr[i]에 대해 같은 값인지 확인한다.
                - 같으면 계속.
                - 다르면 시작 index를 1 늘리고, 1번으로 감.

    */

    return 0;
}

//////////////////////

int main(void) {
	// cin.tie(0);
	// cout.tie(0);
	// std::ios_base::sync_with_stdio(0);
	
	// number of test cases
    getPrime();
    
	int t; cin>>t;
    for(int i = 1; i<=t; i++){
        cout<<"Scenario "<<i<<": \n";
        cout<<solve()<<"\n\n";
    }

	return 0;
}

 

시간복잡도

 n이 1천만. 소수 판정에는 O(nloglogn)이 걸린다.

 소수 개수는 약 70만 개이다. 이를 k라고 두면, 각각의 n$_i$에 대해 sliding window는 O(k), map에 넣을 때는 O(klogk)이다. 이를 m번 돌리므로 O(mklogk), 충분하다.

 

공간복잡도

 primes vector와 map의 size는 worst case O(k). isPrime은 O(n)이므로

 O(n)이다. 

 

후기

 이 문제를 오래 붙잡은 이유는... 메모리 초과는 그렇다 치더라도 scenario를 senario라고 적었기 때문이다.ㅋ.ㅋ.ㅋ.

 

 

 

Leetcode 33. Search in Rotated Sorted Array

 풀면서 엄청 신기했던 문제. 우리가 알고 있는 상식으로는 binary search는 정렬된 상태여야만 쓸 수 있다. 그러나 이 문제에서, rotated된 array에서 binary search를 쓸 수 있다!

1. 어떤 index를 pivot으로 rotate했는지 binary search로 찾는다. 이 때 nums[mid]와 nums[end]를 비교한다.
   • nums[end]가 더 크면 앞으로 당긴다. mid부터 end까지는 오름차순으로 잘 정렬되어 있다는 것이기 때문이다.
   • nums[end]가 nums[mid]보다 더 작으면 뒤로 당긴다. mid부터 end 사이에 pivot이 있다는 의미이기 때문이다.
   • 그러면, binary search 결과는 pivot을 리턴한다.
2. pivot을 축으로 binary search를 진행한다.
   • 단, 원래 하던 것과 같이 binary search를 하면 안 되므로, mid를 얻어낸 후에는 rotated된 array에 있는 값을 얻어오기 위해 (mid + pivot) / nums.size()를 한다.

// Runtime 0 ms Beats 100%
// Memory 11.2 MB Beats 13.70%

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int start = 0, end = nums.size() - 1;
        while(start < end){
            int mid = (start + end)/2;

            if(nums[mid] < nums[end]) end = mid; // 앞으로 당김
            else start = mid + 1;
        }
        cout<<end<<endl;
        // result : 작아진 첫 idx

        int pivot = end;
        // 이걸 사용해서 circular처럼 쓸 수 있음.
        start = 0; end = nums.size()-1;
        while(start <= end){
            int mid = (start + end)/2;
            int idx = (mid + pivot) % nums.size();
            if(nums[idx] == target) return idx;
            if(nums[idx] > target) end = mid - 1;
            else start = mid + 1;
        }
        
        return -1;
    }
};

 

시간복잡도

 O(logn)

 

후기

 신세계다. 이런 기법이 있다니.