[비트 연산 (Bitwise)] LC #136 Single Number

문제 설명

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

 

Example 1:

Input: nums = [2,2,1]
Output: 1

Example 2:

Input: nums = [4,1,2,1,2]
Output: 4

Example 3:

Input: nums = [1]
Output: 1

 

Constraints:

문제 링크: https://leetcode.com/problems/single-number/

1. 문제의 핵심: XOR 비트 연산의 마법

이 문제는 "선형 시간 복잡도(O(N))"와 "상수 공간 복잡도(O(1))"라는 제약 조건이 핵심입니다. 이 두 가지를 모두 만족시키려면 해시맵(O(N) 공간)이나 정렬(O(N log N) 시간)을 사용할 수 없습니다. 정답은 바로 **XOR(^) 비트 연산**에 있습니다.

핵심 아이디어: XOR 연산은 같은 수를 두 번 XOR하면 0이 되고, 어떤 수를 0과 XOR하면 자기 자신이 되는 속성을 가진다. 배열의 모든 요소를 누적하여 XOR하면, 두 번씩 나오는 숫자들은 모두 0으로 상쇄되고 마지막에 유일한 숫자 하나만 남는다.

2. 해결 전략

  1. 결과를 저장할 변수(예: result)를 0으로 초기화합니다.
  2. 주어진 배열 nums의 모든 숫자를 순회합니다.
  3. 각 숫자를 result 변수에 계속해서 XOR 연산(result = result ^ num)을 수행합니다.
  4. 반복문이 끝나면 result에 최종적으로 남는 값이 바로 한 번만 등장하는 유일한 숫자입니다.

3. Java 코드 구현


class Solution {
    public int singleNumber(int[] nums) {
        int result = 0;
        for (int num : nums) {
            result = result ^ num;
        }
        return result;
    }
}

💡 코드 세부 포인트