[C언어 풀이] Codility - Lessons 2, (Arrays) OddOccurrencesInArray

이 문제는 Codility 사이트에서 확인하고 문제를 풀 수 있습니다.

https://www.codility.com/

 

 

 

문제.

 

설명

 

처음에 문제를 받고 번역기를 통해 문제를 접했을 때 '이게 뭔 소리지?' 라고 느꼈습니다.  문제의 규칙도 잘 이해가 안가고....

그러다가 인터넷에 다른사람이 어떻게 풀었는지 보고, 몇번의 실행과정을 거치니 이해가 갔습니다.

 

쉽게 설명하자면!!

1. 홀수개의 배열이 주어집니다.(무조건)

2. 홀수개의 배열 요소중(정수) 단 하나의 요소만 제외하곤 모두 중복되는 숫자입니다.

ex)[1,1,2,2,4,5,5] = 4, [1,2,3,4,5,6,1,2,3,4,5] = 6, [1,2,1,2,2,2,3,2,3,2,7] = 7

3. 중복되는 숫자를 제외한 값을 리턴하면 됩니다.

4. 중복되는 숫자는 2개씩 짝을 이루게 됩니다.

ex)[1,3,2,3,1,2,4] 이렇게 배열 요소가 있다면,

a[0]과 a[4]이 짝, a[1]과 a[3]이 짝, a[2]와 a[5]이 짝. 이런식으로

 

즉, 배열요소중 짝이 없는 정수 1개를 찾아라!! 입니다.

 

 

 

 

결과.

 

https://app.codility.com/demo/results/trainingXSY35A-BEZ/

 

 

 

 

 

소스 코드

 

int solution(int A[], int N) {
    int i, result = 0;
     
    for(i = 0; i < N; i++)
        result ^= A[i];
     
    return result;
}​

 

우선, 제 힘으로 푼 문제가 아닙니다. 문제 자체가 이해가 가질 않아 구글링을 통해 문제 관련 자료를 찾던 중

누가 풀어놓은 소스코드를 봤고, '아차!! ' 하고 깨달으면서 제 자신의 부족함을 느꼈습니다.

애초에 짝을 이뤄 중복되는 숫자를 지우고 하나의 숫자만을 남기게 하려면 XOR로 해결이 가능하고,

제가 이걸 진작에 알았다면 관련 자료를 찾지는 않았을 것입니다.

 

그래도 문제 풀이에 대해 이해는 했으니 적어보겠습니다.

 

XOR은 암호화 할때도 주로 쓰이는 알고리즘 입니다. 중복을 제거할때도 좋은 녀석이죠.

XOR은 숫자가 같으면 0, 숫자가 다르면 1을 반환합니다.

ex) 1111 xor 1111 = 0000,  1010 xor 1010 = 0000,   0101 xor 1010 = 1111.

 

저 문제 풀이방법은 result라는 변수에 어떤 정수와 xor을 하면 순서와 상관없이 

'한 요소'를 제외한 모든 요소가 중복을 제거하게 되고(0으로 만들어 버리죠),

마지막엔 중복이 안된 한 요소만 남게되는 것입니다.