136. Single Number

 

📌 Problem Link :

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

 

✅ Accepted :

class Solution {
    public int singleNumber(int[] nums) {
        int n = nums.length;
        if (n == 1) return nums[0];

        Arrays.sort(nums);
        Deque<Integer> dq = new ArrayDeque<>();
        for (int num: nums) {
            dq.addLast(num);
        }

        while(dq.size() > 1) {
            int first = dq.pollFirst();
            int second = dq.peekFirst();
            if (first == second) {
                dq.pollFirst();
            } else {
                dq.addLast(first);
            }
            
        }
        return dq.peek();
    }
}

 

🧐 Review :

 LeetCode 136번 문제는 입력 값으로 주어진 nums 배열에서 딱 한 번만 나타나는 숫자를 찾아서 반환하는 문제입니다.

문제에서 중요한 제약 조건은 다음 두 가지로 시간 복잡도를 O(N), 공간 복잡도를 O(1)로 풀어야 합니다.

문제를 풀 때 시간복잡도를 O(N)으로 푸는 것에 집중하다보니 Deque를 사용해서 풀면 공간 복잡도가 O(N)이 된다는 것을 문제를 풀고 나서 깨달았습니다. 

 

문제에서 명시적으로 공간 복잡도 O(1)을 요구하고 있기 때문에, Deque를 사용한 풀이는 엄밀한 의미에서 문제의 조건을 충족하지 못한 풀이라고 생각합니다.

 

아래는 해당 문제의 정답 풀이 코드입니다.

class Solution {
    public int singleNumber(int[] nums) {
        int result = 0;
        
        for(int i = 0; i < nums.length; i++) {
            result = result ^ nums[i];
        }
        return result;
    }
}

 

이 풀이는 비트 연산자 XOR(^)의 성질을 활용한 방식입니다.

XOR 연산은 다음과 같은 특징을 가지고 있습니다.

 

• a ^ a = 0
• a ^ 0 = a
• 교환법칙, 결합법칙이 성립

 

문제의 조건상,

 

• 한 숫자를 제외한 모든 숫자는 정확히 두 번씩 등장합니다.
• 동일한 숫자끼리 XOR 연산을 수행하면 0이 되므로 모두 상쇄됩니다.
• 결과적으로 한 번만 등장한 숫자만 result에 남게 됩니다.

 

이 방식은

 

• 배열을 한 번만 순회하므로 시간 복잡도 O(N)
• 추가 변수 result 하나만 사용하므로 공간 복잡도 O(1)

 

문제의 조건을 정확하게 만족하는 풀이입니다.