[Codility] Lesson15 - Caterpillar method: Abs Distinct

Problem

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.

  Copyright 2009–2021 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

How to solve

- 정보

정수로 이루어진 배열 A가 주어짐

 

- 구해야 하는것?

배열 A의 distict absolute value의 갯수 구해라!

 

- 예시

A[0] = -5

A[1] = -3

A[2] = -1

A[3] = 0

A[4] = 3

A[5] = 6

A가 위와 같이 주어졌을 때, 각 원소에 절대값을 한 수들 중 distinct value의 갯수를 return!

 

즉,  0, 1, 3, 5, 6 => 5개 5를 return 한다. 

첫 번째 시도!

Solution1(c++)

1. 각 원소에 절대값을 씌운 값 abs_val 을 구한다.

2. absDistinct 벡터를 만들어, 벡터에 abs_val이 있는지 체크한 후 abs_val 을 넣는다. 

// you can use includes, for example:
#include <bits/stdc++.h>

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
vector<int> absDistinct;
int solution(vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)
    int len = A.size();
    for(int i=0; i<len; i++){
        int abs_val= abs(A[i]);
        if(find(absDistinct.begin(), absDistinct.end(), abs_val) == absDistinct.end()){
            absDistinct.push_back(abs_val);
        }
    }
    int res = absDistinct.size();

    return res;
}

Test Result1

퍼포먼스가 ㅠㅠ

app.codility.com/demo/results/training7EH27C-93D/

두 번째 시도!

Solution2(c++)

key값의 중복을 허용하지 않는 set container를 이용!!

set container?
- associative container중 하나
- 노드 기반 컨테이너로 균형 이진트리로 구현됨
- 중복이 허용되지 않는 key로 이루어진 컨테이너
- 원소(key)가 삽입되면 원소는 자동으로 정렬됨

// you can use includes, for example:
#include <bits/stdc++.h>

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
set<int> absDistinct;
int solution(vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)
    int len = A.size();
    for(int i=0; i<len; i++){
        int abs_val= abs(A[i]);
        absDistinct.insert(abs_val);
    }
    int res = absDistinct.size();

    return res;
}

Test Result2

app.codility.com/demo/results/trainingH724PU-35M/

Test results - Codility