Find the odd int<6 kyu>

jjanmo·2020년 1월 2일

문제

Given an array, find the integer that appears an odd number of times.
There will always be only one integer that appears an odd number of times.

🚩 문제해석
주어진 배열에서 '홀수'번 반복되는 수를 찾으시오.

문제접근

첫번째 코드

function findOdd(A) {
    A.sort();
    for(let i = 0; i < A.length; i++){
      if(A.indexOf(A[i]) === A.lastIndexOf(A[i])) return A[i];
    }
}

첫번째 포스트인 Duplicate Encoder 문제를 풀이 할 때 굉장히 sexy code를 기억하고 있는데, 그 코드가 위에 indexOf()와 lastIndexOf()를 사용한 코드였다. 물론 이 코드는 O(n^2)이기때문에 비효율적인 코드임에는 분명하지만, 배열에서 1개만 있는 요소를 찾을 때 사용하여 결과를 도출하기에 적합한 코드였다. 하지만 이 코드는 문제에서 부적합 판결을 맞았다. 왜? 바로 문제를 정확히 이해하지 못했기 때문이다. 홀수번 나오는 숫자를 찾는거지 1번만 나오는 숫자를 찾는 것이 아니였던 것이다.

두번째 코드

function findOdd(A) {
   A.sort();
   for(let i = 0; i < A.length; i++){
    if((A.lastIndexOf(A[i]) - A.indexOf(A[i])) % 2 === 0) return A[i]; 
   }
}

	> 위의 코드를 약간 수정하였다. 홀수번 나오는 수를 골라낼 수 있도록 indexOf()의 값과 lastIndexOf()의 값 간의 차를 이용하였다.

Best Solution

	const findOdd = (xs) => xs.reduce((a, b) => a ^ b);

이 코드 하나로 끝났다. '^' 연산자라는 것은 알고 있었다. 단, 사용을 해보진 않고 '그냥 아 그런거구나' 하고 넘어간 적이 대부분이였다. 굳이 이걸 사용안하고도 문제가 풀렸을뿐만 아니라 비트 연산자를 자유자재로 사용할 만큼의 능력이 안되었기 때문에 그랬던 것 같다. 이제는 좀 알아보자. 이 부분의 설명에 대해선 외국인 친구가 실제 페이지 풀이 밑에 아주 자세히 적어놓았다.(그래서 spoiler tag를 받았다는...) 이를 참고하여 적는다.

비트연산자란?
비트 연산자는 피연산자를 10진수, 16진수, 8진수처럼 취급하지 않고 32비트의 집합으로 취급한다. 예를 들면, 10진수의 9는 2진수의 1001로 나타낼 수 있다. 비트 연산자는 이진법으로 연산을 수행하지만 결과값은 javaScript의 표준 숫자값(우리가 알고있는 값 : 10진수)을 반환한다. 비트연산자에는 &, |, ^ ~, <<, >> 등이 있다.
a ^ b의미
배타적논리합(XOR : eXclusive OR)이라고 한다. 두 피연산자의 각 자리의 비트의 값이 같을 경우 해당하는 자리에는 0을 준다. 반대로 두 피연산자의 각 자리의 비트의 값이 다를 경우는 1을 반환한다. 예를 들어서 10진수끼리 비교한다고 5 ^ 5 는 비트의 모든 자리가 같기 때문에 결과값으로 0이 된다. 5 ^ 7 이라고 하면 그 값은 0은 아니다.(구체적인 값을 알고자 하면 2진수로 변환 후에 계산을 하면 되지만, 여기선 그렇게까지 할 필요는 없다.)
a ^ b ^ c = a ^ c ^ b or a ^ b ^ c ^ d = a ^ c ^ d ^ b
연산의 순서가 바뀌더라고 피연산자가 바뀌지 않으면 결과값이 변하지 않는다.(같은 연산자가 나왔을 때, 왼쪽에서 오른쪽으로 혹은 오른쪽에서 왼쪽으로 계산할건지를 정하는 것을 결합성(associativity )이라고 한다. 위의 성지로 이로부터 파생된 것이다.)
위의 3가지를 토대로 실제값을 계산해보면, [1,2,3,3,2,3,1] 라는 배열이 주어졌다고 하자.
- 1 ^ 2 = A 라는 결과값이 나온다.
- A ^ 3 = B 인데 이걸 풀어 쓰면 A ^ 3 ^ 3 = A ^ 0 = A 가 된다.
- 배열의 4개의 요소를 연산한 결과값은 A이다.
- A ^ 2 = 1 ^ 2 ^ 2 = 1 ^ 0 = 1 이라는 결과가 된다.
- 남은 요소를 다 쓰면 1 ^ 3 ^ 1 = 1 ^ 1 ^ 3 = 0 ^ 3 = 3
- 최종 결과값은 3이 된다.
이를 바탕으로 생각해보면 짝수번(2,4,6..)나오면 2개씩 XOR연산을 하면 0이 되고 홀수번 나오면 무조건 2개씩 연산하고 남은 1개의 수(혹은 그냥 1개의 수)가 나오게 됨을 알 수 있다. 이를 바탕으로 주어진 배열을 reduce()를 통해서 XOR연산을 하면 모든 연산의 결과로 홀수번 있는 수의 값이 나오게 된다.

결론

비트연산은 이진 파일 포맷 분석, 해시, 암호화 등이 아닐 경우 거의 사용되지 않는다. 그래서 보통 비트연산에 대해서 다른 연산자에 비해 정확히 이해하려는 노력을 들이지 않는다. 나 역시 그랬다. 그렇기 때문에 이러한 풀이를 생각해보려고 하지도 않았다. 아마 앞으로도 생각하기 힘들 것이다.(아마 고급언어를 다루다보니 비트연산을 다룰 일이 그만큼 없어진 것도 한 몫하는 것 같다. 자기합리화..😓) 그럼에도 비트연산은 속도라는 큰 장점을 가진 연산과정이다. 그렇기 때문에 앞으로 깊이 있는 공부를 하다보면 언제가는 마주하게 될거라고 생각한다. 그 때를 위해서 지금 나오는 것만이라도 정확히 이해하고 넘어가야겠다.