문제 링크 : https://www.hackerrank.com/challenges/sansa-and-xor/problem

배열을 요소 한 개, 두 개, 세 개씩 묶어 순회하며 XOR값을 계산하고 각 계산값을 모두 XOR 값을 계산하는 문제이다. 처음엔 for문을 세 번 사용해 모든 계산을 무식하게 수행하도록 작성했는데, XOR 계산의 특징을 활용해 다른 방법을 찾아보기로 했다.

1) 문제 파악하기

교환법칙과 결합법칙

먼저 XOR 연산은 교환법칙과 결합법칙이 성립하는 연산이다. 따라서 본 문제의 계산 식에서 순서를 마음대로 뒤바꿔도 결과가 달라지지 않는다. 교환법칙은 아래와 같다.

자기 자신, 0과의 연산

XOR은 bit 연산 중에서 동일한 위치의 숫자가 같으면 0을, 다르면 1을 반환하는 연산이다. 따라서 자기 자신과 연산을 하면 0, 0과 연산하면 자기 자신이 나오는 특징이 있다.

그래서...

문제의 예시와 함께 주어진 연산을 그대로 하면 앞서 언급한 교환법칙과 계산 특징을 살려 아래와 같이 계산을 할 수 있다.

이렇게 자기 자신들과 연산을 먼저 하게 하면 홀수 번 등장하는 숫자는 자기자신이, 짝수 번 등장하는 숫자는 0이 나와 연산에 영향을 끼치지 않는 것을 볼 수 있다. 따라서 각 원소의 등장 횟수가 중요함을 파악할 수 있었고 이를 계산해보고자 했다.

2) 구현하기

일반항 만들기

임의의 원소 $n$개를 갖는 배열에서 $k$번째 원소가 등장하는 횟수를 $a_k$라 하자. 주어진 배열을 $[1, 2, 3, 4, \cdot\cdot\cdot, n]$라 하면 먼저 한 번에 선택하는 원소의 개수별로 아래와 같이 그룹화할 수 있다.

위에서 1은 모든 그룹에 한 번씩 등장하므로 $a_1 = n$이 된다. 다음으로 2는 첫 번째와 마지막에만 한 번 등장하고 나머지는 두 번씩 등장하므로 $a_2 = 1 + (n - 2) \times 2 + 1 = 2n - 2$가 된다. 3까지 살펴보면 첫 번째와 마지막에 한 번, 두 번째와 마지막에서 두 번째에 두 번, 그리고 나머지에서 세 번씩 등장하므로 $a_3 = 1 + 2 + (n - 3) \times 3 + 2 + 1 = 3n - 6$이 되며, $a_k$는 다음과 같이 계산할 수 있다.

그래서 언제 코드 짤건데...

$a_k$를 잘 살펴보면 $n$이 짝수일 때는 $k$가 짝수든 홀수든 상관 없이 항상 짝수가 되므로 xor연산을 모두 한 결과가 0이 됨을 알 수 있다. 반대로 $n$이 홀수일 때는 $k$가 짝수면 $a_k$가 짝수, $k$가 홀수면 $a_k$가 홀수가 된다. 따라서 핵심은 $n$이 홀수일 때 홀수번째 요소들만 차례대로 XOR 계산을 하면 되는 것이다!

function sansaXor(arr) {
  // Write your code here
  if (arr.length % 2 === 0) return 0;

  const oddPosNumbers = arr.filter((_, i) => i % 2 === 0);
  return oddPosNumbers.reduce((acc, cur) => acc ^ cur, 0);
}

3) 설명이 너무 길어...

엄청 간단한 문제인 것에 비해 일반항까지 계산하며 장황하게 설명했지만, 코테 공부의 묘미가 이런 것이 아닌가 생각한다. 문제에 대해 정확히 이해하고 이해를 바탕으로 모델링을 하고, 그것을 코드로 구현하는 것을 연습하는 과정 말이다. 앞으로도 문제들을 재밌게 바라보고 풀 수 있으면 좋겠다.