220623 [알고리즘] codility _ OddOccurrencesInArray (배열의 홀수 발생) / JavaScript

 

 

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.

 

(국문)

N개의 정수로 구성된 비어 있지 않은 배열 A가 제공됩니다. 배열에는 홀수개의 요소가 포함되어 있으며, 배열의 각 요소는 짝을 이루지 않은 상태로 남아 있는 한 요소를 제외하고 동일한 값을 가진 다른 요소와 짝을 이룰 수 있습니다.

예를 들어 다음과 같은 배열 A에서:

  A[0] = 9 A[1] = 3 A[2] = 9
  A[3] = 3 A[4] = 9 A[5] = 7
  A[6] = 9

인덱스 0과 2에 있는 요소의 값은 9이고,
인덱스 1과 3에 있는 요소의 값은 3이고,
인덱스 4와 6에 있는 요소의 값은 9이고,
인덱스 5의 요소는 값이 7이고 쌍을 이루지 않습니다.
함수 작성:

기능 솔루션(A);

위의 조건을 충족하는 N개의 정수로 구성된 배열 A가 주어지면 짝을 이루지 않은 요소의 값을 반환합니다.

예를 들어, 주어진 배열 A는 다음과 같습니다.

  A[0] = 9 A[1] = 3 A[2] = 9
  A[3] = 3 A[4] = 9 A[5] = 7
  A[6] = 9

함수는 위의 예에서 설명한 대로 7을 반환해야 합니다.

다음 가정에 대한 효율적인 알고리즘을 작성하십시오.

N은 [1..1,000,000] 범위 내의 홀수 정수입니다.
배열 A의 각 요소는 [1..1,000,000,000] 범위 내의 정수입니다.
A 의 값 중 하나를 제외한 모든 값이 짝수번 발생합니다.

 

2.문제 풀이

처음에는 간단하게... 시작을 하였다.

function solution(A) {
    for(let i = 0; i < A.length; i++) {
        if(A[i] !== A[i+2]) {
            return result = A[i+2];
        }
    }
}

그냥 예시 문제의 답만 맞출 수 있는 말도 안돼는 해답이었다^^

 

하지만 결국 시간내에 해결하지 못했고

사람들의 풀이를 찾아보니 reduce를 활용해서 짝이 맞는 숫자의 개수를 오브젝트로 저장하여 그 중에 짝이 없는

즉, 개수가 1개인 것을 찾아내는 방식을 사용하였다.

 

그러기에 앞서 reduce로 개수를 찾아 더해주고 그것을 오브젝트로 저장했는데

예를들면, 아래처럼 1은 2개, 2는 2개, 3은 1개, 4는 2개 로 배열에서의 해당 값들의 개수를 키, 밸류로 다시 만들었다.

result = {

1 : 2,

2 : 2,

3 : 1,

4 : 2,

}

 

그렇게 한 후에 for in을 써서 2로 나눴을 때 나머지가 남는 수를 반환하였다.

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)
    }
}