[Codility] OddOccurrencesInArray

문제 링크 : https://app.codility.com/programmers/lessons/2-arrays/odd_occurrences_in_array/

 

내 풀이 :

소팅한 뒤에 숫자의 갯수를 카운팅한다. 숫자가 달라질 때 카운팅 한 갯수가 홀수면은 짝이 없는 걸로 판별하고 해당 숫자를 반환한다. 배열의 끝까지 검색했다면 마지막 숫자가 짝이 없는 숫자이므로 마지막 숫자를 반환한다.

int solution(vector<int>& A)
{
    // Implement your solution here
    sort(A.begin(), A.end());

    if (A.size() == 1)
    {
        return A[0];
    }

    int count = 0;
    int unpairedNum = 0;
    int prevNum = 0;

    for (auto num : A)
    {
        if (prevNum != num)
        {
            if (count % 2 == 1)
            {
                return prevNum;
            }
            else
            {
                count = 1;
                prevNum = num;
            }
        }
        else
        {
            ++count;
        }
    }

    return A[A.size() - 1];
}

더 좋은 풀이:

소팅을 한 뒤에 인덱스 0번 부터 시작하여 +2 씩 더하며 배열을 탐색한다. +2 인덱스의 값이 이전과 다르다면 짝이 없는 걸로 판별하고 이전 숫자는 짝이 없는 숫자인 것이다.

예를 들어 {2, 2, 3, 9, 9} 배열은 2번 인덱스의 숫자가 3, 그리고 +2인 인덱스 4번의 값이 9 이므로 숫자 3이 짝이 없는 숫자이다. 진짜 똑똑하다 ☺

int solution(vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)
    sort(A.begin(), A.end());
    
    for(int i=0; i<A.size(); i=i+2){
        if(A[i] != A[i+1]){
            return A[i];
        }
    }
}