Lesson 6. Sorting - Distinct

1. 문제

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

 

중복값 제거 문제

예) return 3

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

 

Vector A에서 중복값을 제거하면 {1, 2, 3} 3개가 남는다.

 

2. 매개변수 조건

• Vetor A 크기: 0 ~ 100,000
• Vetor A 요소 값 범위: -1,000,000 ~ 1,000,000

 

3. 코드

• map을 이용한 코드

#include <map>

int solution(vector<int> &A) {
    
    map<int, int> distinct_values = {};

    for(const auto& v : A)
    {
        auto it = distinct_values.find(v);
        if(it == distinct_values.end()) distinct_values.insert(pair<int, int>(v, 1));
        else it->second += 1;
    }

    return distinct_values.size();
}

 

 

• 인접한 중복값 제거 함수(unique) 사용

#include <algorithm>

int solution(vector<int> &A) {
    
    sort(A.begin(), A.end());
    auto last = unique(A.begin(), A.end()); // 중복으로 간주되는 첫번째 요소의 iterator 반환
    int idx = distance(A.begin(), last); // iterator간의 거리(index) 구하기

    return idx;
}