[Lesson 6] Distinct

 

문제

Write a function
int solution(vector<int> &A);
that, given an array A consisting of N integers, returns the number of distinct values in array A.
For example, given array A consisting of six elements such that:
A[0] = 2
A[1] = 1
A[2] = 1
A[3] = 2
A[4] = 3
A[5] = 1

the function should return 3, because there are 3 distinct values appearing in array A, namely 1, 2 and 3.
Write an efficient algorithm for the following assumptions:
N is an integer within the range [0..100,000];each element of array A is an integer within the range [−1,000,000..1,000,000].

 

문제 해석을 잘못해서 시간낭비 했던 문제..ㅠㅠㅠ 제대로! 명확하게 해석하고 문제에 접근하자!!!!!

 

 

풀이

정렬 후, 이전 요소와 다를 시 카운트 하면 된다.

배열이 비어있을 경우 탐색이 안되는 점을 고려해 리턴값을 0으로 예외처리 해야한다.

// you can use includes, for example:
// #include <algorithm>

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

int solution(vector<int> &A) {
    // Implement your solution here
    int cnt = 1;

    if(A.empty()) return 0;

    sort(A.begin(), A.end());

    for(int i = 1; i < A.size(); i++)
    {
        if(A[i-1] != A[i])
            cnt ++;
    }

    return cnt;
}