Knowledge Map

배열중 1개씩만 존재하는 숫자 2개를 찾아내기. 본문

알고리즘

배열중 1개씩만 존재하는 숫자 2개를 찾아내기.

2018. 5. 7. 13:23

하나의 배열중 1개만 존재하는 하나의 숫자는 찾는 것은 XOR로 찾아내면 된다.

하지만 2개가 존재할 경우에는 어떻게 찾아야 할까? 이것도 XOR로 찾아내면 된다. 단, 2번의 loop가 필요하다.


/* 1개 존재하는 숫자가 1개 있을 경우 */
var arr1 = [1,3,2,4,1,3,2,4,20]
console.log(arr1.reduce( (p,a)=>p^a, 0));  // 20
 
/* 1개 존재하는 숫자가 2개 있을 경우 */
var arr2 = [1,3,2,4,7,1,3,2,4,10];
console.log(arr2.reduce( (p,a)=>p^a, 0));  // 13이나온다. 답이 아님
cs



1개 짜리 숫자 2개가 xor연산이 되어버린다. 위의 예시를 보자면 7 ^ 10 = 13


  7 = 이진수   111

10 = 이진수 1010

13 = 이진수  1101


xor 특성상 1이 홀수개가 존재할 경우에 1이 존재하게 된다. 즉 모든 값들을 xor했을 때 1이 존재하는 것은 해당 값이 홀수개가 존재한다는 것이다.

그렇기에 1을 기준으로 xor 연산을 하게 될 경우 하나의 값은 찾을수 있게 된다. 



/* 1개 존재하는 숫자가 2개 있을 경우 */
var arr2 = [1,3,2,4,7,1,3,2,4,10];
 
function arrXor(arr) {
    return arr.reduce( (p,a)=> p^a, 0 );
}
 
 
function separateTwoNum(num, arr) {
    // 비트중 가장 오른편의 1인 값을 가져온다.
    var one = num & (-num);
 
    // 위에서 구한 값이 존재하는 숫자들을 xor하면서 홀수개인 둘중 하나의 숫자를 찾는다.
    var oneNumber = arr.reduce( (p, a) => (one&a) === 1 ? p^a:p, 0);
 
    // 나머지를 xor 연산해서 반환한다.
    return [oneNumber, num ^ oneNumber];
}
 
separateTwoNum( arrXor(arr2), arr2); // [7, 10]
 
cs


Comments