코딜리티 - Distinct(c++)

문제

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].

 

풀이

N개의 중복되는 원소 중에서 고유 원소의 개수를 반환하는 문제

정렬 후 인접한 원소끼리 비교하여 다른 값이면 고유 값이 바뀌는 구간이므로 카운트를 1씩 증가해나간다.

시간복잡도 : sort를 이용한 퀵정렬 평균 nlogn + 인접 원소 비교 n-1번

상수 무시

=> O(N*log(N)) or O(N)

#include <algorithm>
#include <iostream>

int solution(vector<int> &A) {
    
    if(A.empty()) return 0;
    
    int answer = 1;
    
    sort(A.begin(), A.end(), less<int>());
    
    for(int i=0; i<int(A.size())-1; i++){
        if(A[i] != A[i+1]) ++answer;
    }
    
    return answer;
}