파이썬으로 배열에서 한 번만 등장하는 숫자 찾기 — XOR 연산 완벽 가이드

배열 A가 주어졌다고 가정해 봅시다. 이 배열에는 대부분의 숫자가 두 번씩 등장하지만, 딱 하나의 요소만 한 번만 등장합니다. 우리의 목표는 바로 이 유일한 요소를 찾아내는 것입니다.

예를 들어 A = [1, 1, 5, 3, 2, 5, 2]라면 출력 결과는 3이 됩니다. 1, 5, 2는 각각 두 번씩 나타나지만 3은 한 번만 존재하기 때문입니다.

XOR 연산이 답인 이유

모든 숫자가 짝수 번 등장한다는 점이 핵심 힌트입니다. XOR(배타적 OR) 연산은 다음과 같은 성질을 가집니다.

• y XOR y = 0 : 같은 값을 두 번 XOR하면 0이 됩니다.
• y XOR 0 = y : 어떤 값과 0을 XOR하면 자기 자신이 됩니다.
• XOR은 교환 법칙과 결합 법칙이 성립하므로 연산 순서와 무관하게 결과가 같습니다.

따라서 배열의 모든 요소를 차례대로 XOR하면, 두 번 등장한 숫자들은 서로 상쇄되어 0이 되고, 최종적으로 한 번만 등장한 숫자만 남게 됩니다.

풀이 알고리즘

해결 과정은 매우 간단합니다.

1. 결과를 저장할 변수를 res = 0으로 초기화합니다.
2. 배열 A의 각 요소 e에 대해 res = res XOR e를 수행합니다.
3. 모든 반복이 끝난 후 res를 반환합니다. 이것이 곧 정답입니다.

이 방법의 시간 복잡도는 O(n), 공간 복잡도는 O(1)로, 해시맵이나 집합(set)을 사용하는 방식보다 메모리 면에서 훨씬 효율적입니다.

구현 예제

다음 파이썬 코드를 통해 실제 구현을 확인해 보겠습니다.

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        ans = nums[0]
        for i in range(1, len(nums)):
            ans ^= nums[i]
        return ans

ob1 = Solution()
print(ob1.singleNumber([1, 1, 5, 3, 2, 5, 2]))

입력

nums = [1, 1, 5, 3, 2, 5, 2]

출력

3

마무리

XOR 연산을 활용하면 추가 메모리 없이 선형 시간 안에 문제를 해결할 수 있습니다. 비트 연산의 직관적인 성질을 잘 이해하고 있으면 코딩 인터뷰에서 이런 유형의 문제를 빠르고 우아하게 풀어낼 수 있습니다. 배열 대신 functools.reduce(operator.xor, nums)를 사용하면 코드를 더욱 간결하게 작성할 수도 있습니다.