코딜리티(Codility) Lesson2 OddOccurrencesInArray 문제풀기 (javascript)

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.

  Copyright 2009–2021 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

문제를 읽고나서 바로 떠오르는 생각은 정리하면

• 배열에 있는값을 Object로 변환을 해야겠다고 생각했다.
• Key값을 배열에 값으로 정하고 Value를 누적되는 숫자로 쓰기 위해서다.
• reduce가 제일먼저 떠올라서 활용하기로 했다.
• object를 for in 문으로 사용하기로 생각했다.

function solution(A) {
    const result = A.reduce((prev, curr)=>{
        if(prev[curr]){
            prev[curr] = prev[curr] + 1;
        }else{
            prev[curr] = 1;
        }
        return prev;
    },{})

    for( key in result){
        if(result[key] % 2 === 1) return Number(key)
    }
}

해결을 하였지만... 영 찝찝하다.

다른 사람들 해결법을 확인하고 싶었다.
첫번쨰로 찾아본 사람은 Set으로 적용한다음에 object값으로 처리하였는데..
접근법이 굉장히 신선하였다. 덕분에 새로운 시야가 생긴것 같다.

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)
    let element = new Set();
    
    for(let i in A){
        if(!element.has(A[i])){
            element.add(A[i]);
        }
        else{
            element.delete(A[i]);
        }
    }
    
    const result = [...element];
    return result[0];
}

miiingo.tistory.com/263

밑에와 같이 해결한 사람은 천재인듯하다.... 바로 이해가 되지 않았다. 그래서 설명법을 자세히 써놓은 링크를 첨부하였다.

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)
    var result = 0;
    for(var i=0; i<A.length; i++){
        result = result^A[i];
    }
        
    return result;
}

matthewhorne.me/odd-occurrences-in-array/