C# 프로그래밍 기초 실습 전자책

C# / .NET 알고리즘과 퀴즈
본 알고리즘 퀴즈 문제는 C#/.NET 개발자를 위한 알고리즘 인터뷰 혹은 C# 프로그래밍을 통한
문제 해결 알고리즘을 연구해 보는데 도움이 되고자 작성되었습니다.


퀴즈 질문


예상답변/설명

만약 정수 배열이 2,2,4,4,5,5,7,9,9와 같이 소트되어 있다면, 매 2개의 배열 요소를 비교해서 서로 다른 경우 첫번째 요소를 리턴하면 된다. 하지만 배열이 소트되어 있지 않은 경우는 이러한 방법을 쓸 수 없다. 이런 경우 XOR 연산의 특성을 사용하면 쉽게 답을 구할 수 있다. 만약 2개의 숫자가 동일하다면 XOR를 하면 0가 된다. 따라서 모든 배열요소를 XOR하면 서로 쌍을 이루는 숫자는 전부 0이 될 것이므로, 쌍을 이루지 않은 하나의 숫자만 남게 된다.

int FindSingleInt()
{
    int[] arr = { 2, 4, 9, 5, 9, 5, 7, 4, 2 };
    int x = 0;

    for (int i = 0; i < arr.Length; i ++)
    {
        x ^= arr[i];
    }

    return x;
}