[Algorithm] Codility Lesson 2-1

A non-empty array A consisting of N integers is given. The array contains an odd number of elements, and each element of the array can be paired with another element that has the same value, except for one element that is left unpaired.

 For example, in array A such that:

 A[0] = 9  A[1] = 3  A[2] = 9

 A[3] = 3  A[4] = 9  A[5] = 7

 A[6] = 9

 the elements at indexes 0 and 2 have value 9,

 the elements at indexes 1 and 3 have value 3,

 the elements at indexes 4 and 6 have value 9,

 the element at index 5 has value 7 and is unpaired.

 Write a function:

 function solution(A);

 that, given an array A consisting of N integers fulfilling the above conditions, returns the value of the unpaired element.

 For example, given array A such that:

 A[0] = 9  A[1] = 3  A[2] = 9

 A[3] = 3  A[4] = 9  A[5] = 7

 A[6] = 9

 the function should return 7, as explained in the example above.

 Write an efficient algorithm for the following assumptions:

 N is an odd integer within the range [1..1,000,000];

 each element of array A is an integer within the range [1..1,000,000,000];

 all but one of the values in A occur an even number of times.

문제를 해석하자면, 예를 들어 [9, 3, 9, 3, 9, 7, 9] 라는 배열이 있었을 때 

- 0번째 9와 2번째 9와 한 쌍

- 1번째 3과 3번째 3과 한 쌍

- 2번째 9와 6번째 9가 한썽으로 이뤄지며 

쌍이 없는 7을 반환한라 이다. 즉, 배열에 무작위로 숫자들이 나열 되며 그 중에 짝이 없는 숫자를 반환하면 된다.

처음엔 무슨 알고리즘을 써야할지 생각해보지 않고 빈 배열에 짝이 없으면 넣고, 짝이 있으면 빼고를 반복하도록 짜봤다.

const A = [9,3,9,3,9,7,9];

function solution(A) {
    let temp = [];

    A.map((a) => {
        if(temp.indexOf(a) === -1) {
            temp.push(a);
        } else {
            temp.splice(temp.indexOf(a), 1);
        }
    });

    return temp[0];
}

그랬더니 정답은 맞지만, 효율성이 떨어져 66%... ㅠㅠ 

다시 짤땐 quick sort 방법을 사용해 봤다. 

Quick Sort 란 ? 배열 중 아무 값을 잡고(이것을 피벗(pivot)라 하자) 입력 받은 값이 피벗보다 작을 경우 피벗 중심으로 왼쪽으로 클 경우 오른쪽으로 정렬을 반복하는 방법이다. 

설명 잘 되있는 동영상을 참고한다 : https://www.youtube.com/watch?v=7BDzle2n47c

다시 짠 코드는 다음과 같다.

const A = [9,3,9,3,9,7,9];

function solution(A) {
    A.sort((a, b) => { // Quick sort 알고리즘
        if (a < b) {
            return 1; // 내림차순
        } else {
            return -1; // 오름차순
        }
    });

    for (let i = 0; i < A.length-1; i++) {
        let pivot = A[i];
        if (pivot === A[i + 1]) {
            i++;
            continue;
        }
        else
            return pivot;
    }

    return A[0];
}

이렇게 짰더니 드디어 100% 통과 ㅎㅎㅎ

그리고..

혹시나 다른 사람들은 어떻게 생각했나 궁금해서 찾아보니까 XOR 을 써서 신박하게 푼 사람이 있어서 가져와봤다.

XOR 은 값이 서로 다를때만 true 를 반환하고, 서로 같으면 false 를 반환하는 특성을 잘 생각해서 응용한 방법인데

(XOR 설명 : 위키백과 중 진리표 확인)

이건 솔직히... XOR 이 뭔지 알면서 코드를 처음 접했을때도 한번에 이해가 안되더라.. 실무에서 이렇게 만들고 올리면 팀원들이 욕할거가탱..ㅎㅎㅎ

코드는 다음과 같다.

const A = [9,3,9,3,9,7,9];

function solution(A) {
     let result = 0;

    A.map((x) => {
        result ^= x; // XOR 계산
    });

    return result;
}