Codility: FirstUnique 풀이

FirstUnique coding task - Practice Coding - Codility

 

A non-empty array A consisting of N integers is given. The unique number is the number that occurs exactly once in array A.

For example, the following array A:

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

contains two unique numbers (5 and 2).

You should find the first unique number in A. In other words, find the unique number with the lowest position in A.

For above example, 5 is in second position (because A[2] = 5) and 2 is in fourth position (because A[4] = 2). So, the first unique number is 5.

Write a function:

class Solution { public int solution(int[] A); }

that, given a non-empty array A of N integers, returns the first unique number in A. The function should return −1 if there are no unique numbers in A.

For example, given:

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

the function should return 4. There are two unique numbers (4 and 2 occur exactly once). The first one is 4 in position 1 and the second one is 2 in position 5. The function should return 4 bacause it is unique number with the lowest position.

Given array A such that:

A[0] = 6 A[1] = 4 A[2] = 4 A[3] = 6

the function should return −1. There is no unique number in A (4 and 6 occur more than once).

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 [0..1,000,000,000].

 

간단히 말하면 배열에서 고유한, 즉 하나밖에 존재하지 않는 원소 중 가장 인덱스가 작은 원소를 리턴하면 된다.

array element 범위가 0에서 10억까지이므로 모든 값에 대한 occurrences counter array를 만드는 방법은 메모리가 초과된다.

평범하게 O(N ** 2) 방법으로 구현하면 시간초과로 100점중 72점밖에 받지 못한다.

 

#define HASHCOUNTER_BUCKET_COUNT 10000

class HashCounter
{
public:
    void addCount(int key)
    {
    	// 이미 counter element가 존재한다면 value를 1 증가시키고,
    	// 그렇지 않다면 counter element를 새로 만든다.

        int hash = getHash(key);

        bool exists = false;
        for(int i = 0; i < buckets[hash].size(); ++i)
        {
            if(key == buckets[hash][i].first)
            {
                ++buckets[hash][i].second;
                exists = true;
            }
        }

        if(!exists)
        {
            buckets[hash].push_back(make_pair(key, 1));
        }
    }

    int getCount(int key)
    {
    	// counter element가 존재하면 그 value를 리턴하고,
        // counter element가 존재하지 않으면 0을 리턴한다.

        auto hash = getHash(key);

        for(int i = 0; i < buckets[hash].size(); ++i)
        {
            if(key == buckets[hash][i].first)
            {
                return buckets[hash][i].second;
            }
        }
        
        return 0;
    }
private:
    int getHash(int key)
    {
    	// 가장 간단한 해쉬 함수이다.
        
        return key % HASHCOUNTER_BUCKET_COUNT;
    }
private:
    // vector의 element인 pair<int, int>는 counter element로,
    // first element는 key, second element는 counter를 의미한다.
    vector<pair<int, int>> buckets[HASHCOUNTER_BUCKET_COUNT];
};

int solution(vector<int> &A) {
    HashCounter counter;
    int len = A.size();

    for(int i = 0; i < len; ++i)
    {
        counter.addCount(A[i]);
    }

    for(int i = 0; i < len; ++i)
    {
        if(counter.getCount(A[i]) < 2)
        {
            return A[i];
        }
    }

    return -1;
}

 

STL의 map이나 unordered_map을 사용할 수 도 있겠지만 연습을 위해 간단한 해싱을 이용한 Counter 자료구조를 만들었다.

원래라면 체이닝을 이용하여 중복된 원소가 없도록 하지만, 해시 값이 겹치는 값들을 sub array에 저장하도록 구현하였다.