[Arrays] OddOccurrencesInArray

알고리즘 태클 열렬히 환영합니다~

한 수 가르쳐주십쇼~~

[Arrays] OddOccurrencesInArray
URL : https://codility.com/programmers/lessons/2-arrays/odd_occurrences_in_array/

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만 쌍이 없습니다.

아래와 같은 함수를 작성합니다 :

int solution(int A[], int N);

위의 조건을 만족하는 배열 A와 정수 N이 주어졌을 때, 쌍을 이루지 않는 값을 반환합니다.

예를 들어 배열 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 사이의 값입니다.

- 하나의 원소를 제외하고 모든 값들은 짝수번 등장해서 짝을 이룹니다.

- 시간복잡도는 최악의 경우 O(N)입니다.

- 공간복잡도는 최악의 경우 O(1)입니다.

- 배열 A는 수정하실 수 있습니다.

C언어 100% 점수 획득 코드

int solution(int a[], int N) {

int i, temp=0;

for(i=0; i<N; i++) {

temp ^= A[i];

}

return temp;

}

시간복잡도 생각하지 않고 풀다고 하면...

글쎄요... 첫 항목부터 차례로 뒤에 같은 값이 있나 체크하고,

있으면 두 값을 0으로 만들고, 0이면 체크 생략... 없으면 반환값으로 선택해서 답을 구할 수 있으려나요...

이렇게 풀 경우, 총 원소 개수만큼 N의 탐색, 그리고 탐색마다, 현재 위치 i부터 N-i번 탐색...

O(N^2)일 것 같습니다(맞나요?)

XOR연산의 특징을 잘 파악하시고 있으면 어렵지 않게 푸실 수 있습니다.

같은 값을 XOR 할 경우, 0이 되어버리는 특징이 있죠.

이 문제의 경우 모든 값을 XOR시켜버리면, 같은 쌍끼리는 상쇄되어 결국 쌍을 이루지 않는 값 하나만 남게 됩니다.

위 코드에서는 temp에 모든 값을 XOR시켜버립니다.

codility에서 댓글로 서로 소스코드나 의견을 교환하기도 하는데요,

XOR연산이 참 파워풀해서 유용하다는 의견이 많습니다.

알고리즘을 잘하는데 있어서 문제 해결의 아이디어도 중요하지만,

그 못지않게 컴퓨터 연산의 특성이나 수학적 센스도 중요하다는 생각이 드네요.