# OddOccurrencesInArray 코딜리티 레슨 문제

코딜리티 레슨을 푸는중에 나온 문제.

음.. 문제는 간단하게 요약하면 다음과 같다.

어떤 배열 A가 주어지고 이 배열 안에는 N개의 원소가 들어 있다. 이 원소들은 일정한 짝을 이루어 동일한 값을 가지고 있다.

예를 들면 다음과 같다. A[0] = 1, A[1] = 2, A[2] = 1, A[3] = 2 .... 

그리고 이러한 내용에 여러가지 가정된 상황들이 붙는다. 뭐, 각 원소의 값의 범위라던가.

• 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.

이런식으로..

단순하게 생각하면 특정한 한개의 수를 찾는거니, 배열을 순회하며 중복되지 않는 수를 찾으면 된다. 여러가지 방법을 시도했는데

역시나 코드가 지저분해지고 쓸데없이 if문이 포함되기도 했다. 문제에 대해 접근을 잘못했나.. 싶었는데

배열내 원소를 잘보면 반복되는 구조를 가지고 있다. 예를들면 1, 2, 1, 2, 1, 2 이런식으로. 

그렇다면 1,2라는 모양으로 반복이 되니 이 반복과 달라지는 부분에서 원하는 값을 얻을 수 있을거라 생각했다. 이를 바탕으로 접근해보니 뭔가 깔끔한 생각이 떠오르지 않더라.

비트연산을 이용하면 뭔가 좋을 것 같던 참에, 해당 레슨에 대해 comment들을 살펴보았더니 누가 멋진 솔루션에 대한 힌트를 주더라. XOR.. 바로 배타적 논리합 연산이다. 그리고 이를 이용한 매우 짧은 코드를 보여주며, 이게 전부야! 라는 늬앙스로 덧글을 적어놓았다. 샘플 예제로 손으로 계산해보니, 어랍쇼. 답이 나온다.

평소에는 비트 연산이라 하면 &, | 같은 논리적 합,곱만 쓰고 특정 비트를 키거나 끄는 식으로만 했었는데, XOR는 관심도 없었고 써본적도 없었다. 위키에서 찾아보니 비트열에 대해 감가산에 쓰이기도 하더라. 실제로 해보니 감가산의 기능을 한다. 아무튼, 생각보다 쓸모가 많은놈이다. 프로그래밍은 끝이없다.

p.s. XOR연산을 쓴적이 없다고 생각했었는데, 블로그 게시물중에 XOR 연산으로 swap 하는게 있더라ㅋㅋㅋㅋㅋ...이런..

1 2 3 4 5 6 7

int solution(vector<int> &A){ int answer = 0; for(int idx = 0; idx < A.size(); idx++){ answer ^= A[idx]; } return answer; }