Lesson 15. Caterpillar method - AbsDistinct

1. 문제

A non-empty array A consisting of N numbers is given. The array is sorted in non-decreasing order. The absolute distinct count of this array is the number of distinct absolute values among the elements of the array.
For example, consider array A such that:
A[0] = -5
A[1] = -3
A[2] = -1
A[3] = 0
A[4] = 3
A[5] = 6

The absolute distinct count of this array is 5, because there are 5 distinct absolute values among the elements of this array, namely 0, 1, 3, 5 and 6.

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

that, given a non-empty array A consisting of N numbers, returns absolute distinct count of array A.
For example, given array A such that:
A[0] = -5
A[1] = -3
A[2] = -1
A[3] = 0
A[4] = 3
A[5] = 6
the function should return 5, as explained above.

Write an efficient algorithm for the following assumptions:
  - N is an integer within the range [1..100,000];
  - each element of array A is an integer within the range [−2,147,483,648..2,147,483,647];
  - array A is sorted in non-decreasing order.

 

절대값의 개수를 구하는 문제.

 

예시) return 5 (0, 1, 3, 5, 6)

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

 

2. 매개변수 조건

• Vector A 크기: 1 ~ 100,000
• Vector A 요소 값 범위: -2,147,483,648 ~ 2,147,483,647
• Vector A는 오름차순으로 정렬되어 있음. (단, 값이 중복해서 있을 수 있음)

 

3. 문제풀이 전략

음수는 -1을 곱해서 양수로 만든다.

 

 

4. 코드 (C++)

빠른 검색 및 삽일을 위해 unordered_map을 사용했다.

#include <unordered_map>

int solution(vector<int> &A) {

    unordered_map<int, int> absolute_values = {};
    for(size_t i = 0; i < A.size(); i++)
    {
        if(A[i] < 0) A[i] *= -1;
        auto it = absolute_values.find(A[i]);
        if(it == absolute_values.end()) absolute_values.insert({A[i], 1});
    }

    return absolute_values.size();
}

 

 

5. 결과