OddOccrurrencesInArray (짝 없는 원소)

비어있지 않은 정수 배열 A가 주어진다. 배열 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은 짝이 없으므로 남게 됨

따라서 이 배열에서 짝을 이루지 못하는 원소는 7이다.

다음 함수를 작성하라:

class Solution {
    public int solution(int[] A);
}

이 함수는 위 조건을 만족하는 정수 배열 A가 주어졌을 때,
짝을 이루지 못한 원소의 값을 반환해야 한다.

예시:
A = [9, 3, 9, 3, 9, 7, 9]
반환값: 7

조건:
- N은 [1..1,000,000] 범위의 홀수 정수
- 배열 A의 각 원소는 [1..1,000,000,000] 범위의 정수
- 배열 A의 모든 값은 짝수 번 등장하며, 단 하나의 값만 홀수 번 등장한다.

 

 

public class OddOccrurrencesInArray
{
    public int solution(int[] A)
    {
        /*
        XOR 연산 규칙:
        a ^ a = 0(같은 값 두 번 XOR → 소거됨)
        a ^ 0 = a(0과 XOR하면 자기 자신)
        XOR 연산은 순서와 그룹에 상관없음.
        */
 
        int unpaired = 0;
 
        // 배열 돌며 XOR 연산 수행
        foreach (int number in A)
        {
            // 현재까지의 결과(unpaired)와 배열 원소(number)를 XOR
            unpaired ^= number;
 
            // - 같은 값이 두 번 나오면: a ^ a = 0
            // - 0과 어떤 값을 XOR 하면: 0 ^ a = a
            // => 결국 짝수 번 등장한 값들은 모두 사라지고,
            //    홀수 번 등장한 단 하나의 값만 남는다.
        }
 
        // 최종적으로 남은 값이 짝을 이루지 못한 원소
        return unpaired;
    }
}