Lesson 11. Sieve of Eratosthenes - CountNonDivisible #1

1. 문제

You are given an array A consisting of N integers.
For each number A[i] such that 0 ≤ i < N, we want to count the number of elements of the array that are not the divisors of A[i]. We say that these elements are non-divisors.
For example, consider integer N = 5 and array A such that:
A[0] = 3
A[1] = 1
A[2] = 2
A[3] = 3
A[4] = 6

For the following elements:
A[0] = 3, the non-divisors are: 2, 6,
A[1] = 1, the non-divisors are: 3, 2, 3, 6,
A[2] = 2, the non-divisors are: 3, 3, 6,
A[3] = 3, the non-divisors are: 2, 6,
A[4] = 6, there aren't any non-divisors.

Write a function:
vector<int> solution(vector<int> &A);

that, given an array A consisting of N integers, returns a sequence of integers representing the amount of non-divisors.
Result array should be returned as an array of integers.
For example, given:
A[0] = 3
A[1] = 1
A[2] = 2
A[3] = 3
A[4] = 6
the function should return [2, 4, 3, 2, 0], as explained above.

Write an efficient algorithm for the following assumptions:
  - N is an integer within the range [1..50,000];
  - each element of array A is an integer within the range [1..2 * N].

 

배열A에서 A[i]의 약수가 아닌 수의 개수를 찾는 문제.

 

예) return [2, 4, 3, 2, 0]

A[0]	A[1]	A[2]	A[3]	A[4]
3	1	2	3	6

배열A	약수가 아닌 수	약수가 아닌 수의 개수
A[0] = 3	A[2] = 2 A[4] = 6	2
A[1] = 1	A[0] = 3 A[2] = 2 A[3] = 3 A[4] = 6	4
A[2] = 2	A[0] = 3 A[3] = 3 A[4] = 6	3
A[3] = 3	A[2] = 2 A[4] = 6	2
A[4] = 6	없음	0

 

 

2. 매개변수 조건

• 배열A 크기(N): 1 ~ 50,000
• 배열A 요소 값 범위: 1 ~ 2N

 

 

3. 풀이전략

• 배열A를 오름차순으로 정렬한 임시(temp) 배열을 만든다.
• A[i] 값을 temp에서 찾는다.
• A[i] 앞쪽 요소는 약수인지 확인한다
• A[i] 뒤쪽 요소는 약수가 아니다 (중복 값 있는지 확인 필요)
• 계산된 결과는 map에 저장해 둔다. (중복된 요소가 있을 시, 1번만 계산하기 위해)

 

4. 코드 (C++)

#include <map>
#include <algorithm>

vector<int> solution(vector<int> &A) {

    vector<int> result = {}; //결과 저장
    vector<int> temp = A; //임시 배열
    map<int, int> memo = {}; //이전에 계산된 결과 저장

    sort(temp.begin(), temp.end());
    
    for(size_t i = 0; i < A.size(); i++)
    {
        auto it = memo.find(A[i]);
        if(it != memo.end()) //이전에 계산된 결과가 있으면 재활용
        {
            result.emplace_back(it->second);
        }
        else 
        {
            //임시 배열에서 A[i] 값을 찾는다
            auto pos = find(temp.begin(), temp.end(), A[i]);
            int start_idx = distance(temp.begin(), pos);
            int end_idx = start_idx;
            
            //임시 배열에서 A[i]와 중복된 값이 있는지 확인한다
            for(size_t j = start_idx + 1; j < temp.size(); j++)
            {
                //중복된 값이 있으면 index를 뒤로 이동시킨다
                if(temp[j] == A[i]) end_idx++;
                else break;
            }

            //A[i] 뒤에 있는 값은 모두 약수가 아니다
            int cnt = temp.size() - end_idx - 1;
            for(int j = 0; j < start_idx; j++)
            {
                if(A[i] % temp[j] != 0) cnt++;
            }

            //계산된 결과 기록
            memo.insert(pair<int, int>(A[i], cnt));
            result.emplace_back(cnt);
        }
    }

    return result;
}

 

 

5. 결과