LeetCode 136. SingleNumber — XOR 연산 응용

🔍 LeetCode 136번 Single Number

 — Dictionary 풀이 vs XOR 풀이 완전 비교

 

LeetCode 136번 Single Number 문제는 매우 유명한 비트 연산 문제다.

“배열에서 단 한 번만 등장하는 숫자를 찾아라”라는 단순한 요구지만, 효율성과 공간 복잡도에 따라 풀이의 난이도가 크게 달라진다.

 

이 글에서는 직관적인 Dictionary 풀이와 가장 빠르고 메모리 효율이 좋은 XOR 정석 풀이를 비교하여, 어떤 방식이 더 좋은 선택인지 자세히 분석해보겠다.

 

https://leetcode.com/problems/single-number/description/

 

 

---

 

🧩 문제 요약

 

정수 배열 nums에서
오직 한 번만 등장하는 숫자를 찾기.
나머지 숫자는 모두 두 번씩 등장한다.

 

예:

입력:  [2,2,1]
출력:  1

 

 

 

 

---

 

🥇 1. Dictionary(해시맵) 풀이 — 직관적이지만 비효율적인 이유

 

아래는 내가 처음에 풀었던 방식인 Dictionary를 이용한 풀이:

public int SingleNumber(int[] nums)
{
    Dictionary<int, bool> dict = new Dictionary<int, bool>();

    foreach (var i in nums)
    {
        if (dict.ContainsKey(i))
        {
            dict.Remove(i);
        }
        else
        {
            dict[i] = true;
        }
    }

    return dict.Keys.First();
}

 

 

✔️ 장점

①  직관적으로 이해가 쉽다

한 번 나오면 담고, 두 번째 나오면 삭제한다.

결국 마지막에 딱 하나 남는다.

②  논리적으로 오류가 없다

문제 조건(단 한 숫자만 1회 등장)과 정확히 일치한다.

 

 

❌ 단점

①  공간 복잡도 O(n)

짝으로 등장하는 숫자들은 결국 지워지지만,

중간 과정에서 dict에는 여러 숫자가 저장된다.

→ 큰 입력에서는 불필요한 메모리 사용이 커진다.

 

② 성능이 XOR보다 느리다

ContainsKey, Remove는 평균 O(1)이지만,

해시 연산과 리사이징이 일어나기 때문에 실제 실행 비용은 XOR보다 훨씬 크다.

 

③ LeetCode가 의도한 풀이와 다르다

이 문제는 원래 O(1) 공간으로 해결하는 비트 연산 문제이다.

 

 

 

---

 

🥈 2. XOR 정석 풀이 — 가장 빠르고 메모리 효율 최고의 방식

 

LeetCode 토론에서도 공식 인터뷰에서도 가장 많이 언급되는 풀이가 바로 XOR 풀이다.

처음에 이 풀이 보고 미쳤다고 생각했다..(positive)

 

public int SingleNumber(int[] nums)
{
    int result = 0;
    foreach (var n in nums)
    {
        result ^= n;
    }
    return result;
}

 

 

 

✔️ XOR이 가능한 이유 (핵심 성질 3개)

1) a ^ a = 0

같은 숫자는 서로 지워진다.

 

2) 0 ^ b = b

0은 XOR에 영향을 주지 않는다.

 

3) 교환/결합 법칙이 성립한다

순서 상관 없이 모든 숫자를 XOR 해도 된다.

결국 “짝수 번 등장하는 숫자는 모두 사라지고 한 번 등장한 숫자만 남는다.”

 

 

XOR 연산

 

 

✔️ 장점

① 공간 복잡도 O(1)

추가 메모리가 필요 없다.

 

② 시간 복잡도 O(n)

한 번만 순회하면 된다.

 

③ 가장 빠르고 가장 짧다

컴퓨터가 가장 좋아하는 연산: 비트 연산.

 

 

✔️ 단점

① 초보자에게는 직관적이지 않다

사람이 “왜 XOR이 되지?” 하고 이해하는 데 시간이 걸린다.

하지만 일단 이해하면 비트 문제에서 자주 응용된다.