[C++ 풀이] Codility - Lessons 6, (Sorting) Distinct

이 문제는 Codility 사이트에서 확인하고 문제를 풀 수 있습니다.

https://www.codility.com/

 

 

 

문제.

 

 

 

 

 

설명

 

 

배열 A가 주어집니다. 배열의 길이는 0 ~ 100,000 까지 있을 수 있습니다.

배열의 요소는 값 범위는 -1,000,000 ~ 1,000,000 입니다.

 

배열 A의 요소들 중 중복값을 제외한 정수가 몇 개가 있는지 반환하면 되는 문제입니다.

 

위 예제에서는 1, 2 ,3 총 3개가 있으니 3을 return하면 됩니다.

 

 

 

결과

 

 

 

// 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) {
    // write your code in C++14 (g++ 6.2.0)
    
    int count = 0;
    int arr_plus[1000001] = {'\0',};
    int arr_minus[1000001] = {'\0',};
    
    for_each(A.begin(), A.end(),[&](auto& num){
        if(num >= 0){
            if(arr_plus[num] == '\0'){
                count++;
                arr_plus[num] = 1;
            }
        }else{
            if(arr_minus[num * -1] == '\0'){
                count++;
                arr_minus[num * -1] = 1;
            }
        }
    });
    
    return count;
}

https://app.codility.com/demo/results/trainingSYD2QC-5E4/

 

 

 

쉽게 풀긴 했는데 만족스럽지 않습니다.

 

배열의 크기를 최대 100,000으로 맞춰 할 방법을 생각하니 2진트리를 이용한 set밖에 떠오르지 않았습니다.

 

Linked list를 통해 구현하면 되지만...... 시간이 걸리므로(사실 까먹음...)

 

C++의 set을 이용해 풀어봤습니다.

 

찾아보니 퀵정렬로 푸는 풀이법도 존재 했으나 2진트리보다 비 효율 적입니다.

 

// you can use includes, for example:
#include <algorithm>
#include <set>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

using namespace std;

int solution(vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)
    set<int> h_set;
    
    for_each(A.begin(), A.end(), [&](auto& num){
       h_set.insert(num); 
    });
    
    return h_set.size();
}
​

 

https://app.codility.com/demo/results/training25HMZ7-CQC/