137. Single Number II

137. Single Number II

 

내 코드

class Solution:
    def singleNumber(self, nums: List[int]) -> int:        
        hmap = defaultdict(int)

        for n in nums:
            hmap[n]+=1

        for k, v in hmap.items():
            if v == 1:
                return k

 

 

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

선형 런타임 복잡도를 갖는 솔루션을 구현해야 하며, 일정한 추가 공간만 사용해야 합니다.

 

제공한 코드는 정확한 결과를 반환할 수는 있지만,

문제에서 요구한 조건 **(O(n) 시간 복잡도와 O(1) 공간 복잡도)**를 만족하지 않음

---

문제점

1. 공간 복잡도 (O(1) 아닌 O(n))
   • hmap = defaultdict(int)을 사용하여 입력 배열의 숫자들을 키로, 빈도를 값으로 저장하므로, 추가적인 메모리 공간이 필요합니다.
   • 이는 공간 복잡도가 O(n)이 됩니다. 문제에서 요구하는 "constant extra space" 조건을 위반합니다.
2. 해결책 요구 사항 위반
   • 문제에서는 상수 공간을 사용해야 하므로, hashmap이나 추가적인 데이터 구조 없이 문제를 해결해야 합니다.

 

접근 방법

1. O(n) 시간 복잡도:
   • 배열을 한 번만 순회(for, while)해야 함.
2. O(1) 공간 복잡도:
   • 새로운 데이터 구조를 생성하지 않고, 배열을 직접 수정하거나 계산해야 함.

 

Given an integer array nums where every element appears three times except for one, which appears exactly once. 

Find the single element and return it.

모든 요소가 세 번 나타나는 정수 배열 nums가 주어지고, 그 중 하나는 정확히 한 번 나타납니다. 

단일 요소를 찾아 반환합니다.

 

이 문제는 배열에서 모든 숫자가 세 번씩 반복되며, 단 한 숫자만 한 번만 나타나는 숫자를 찾는 문제입니다.

그리고 문제는 O(n) 시간 복잡도와 O(1) 공간 복잡도로 해결해야 한다고 요구합니다.

---

해결 접근법: 비트 연산 활용

배열에 있는 숫자들이 3번 반복된다는 특성을 이용해 각 비트의 합을 계산하고,

3으로 나눈 나머지를 이용하여 한 번만 나타나는 숫자를 알아낼 수 있습니다.

---

알고리즘 설명

1. 비트 합 계산
   각 비트 위치(0~31)에 대해, 배열의 모든 숫자에서 해당 비트가 1인 경우의 합을 계산합니다.
2. 3으로 나눈 나머지
   모든 비트 합을 3으로 나눈 나머지를 구하면, 한 번만 나타나는 숫자의 해당 비트값을 얻을 수 있습니다.
3. 비트 재조합
   이렇게 얻은 나머지 값을 통해 한 번만 나타나는 숫자를 재구성합니다.

 

https://youtu.be/cOFAmaMBVps?si=o75qRljcA7jjOQk5

 

더 쉬운 코드로 문제를 해결하려면, 비트별 계산 대신 세 번 나타나는 숫자를 직접 추적하는 방식을 사용할 수 있습니다. 이 방법은 여전히 O(n) 시간 복잡도와 O(1) 공간 복잡도를 유지하면서, 구현도 간단해집니다.

---

아이디어: 두 개의 비트 추적 (비트 마스크)

이 방법은 비트 마스크를 사용하여, 각 숫자가 등장하는 상태를 두 비트로 표현합니다.

• one: 현재까지 한 번 나타난 숫자를 추적합니다.
• two: 현재까지 두 번 나타난 숫자를 추적합니다.
• 한 번 더 나타나는 숫자는 세 번 반복되므로 다시 제거됩니다.

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        one, two = 0, 0  # 한 번, 두 번 나타난 숫자를 추적
        
        for num in nums:
            one = (one ^ num) & ~two  # num을 추가하면서 two에 있는 숫자는 제거
            two = (two ^ num) & ~one  # num을 추가하면서 one에 있는 숫자는 제거
        
        return one  # 세 번 나타난 숫자는 제거되었으므로 한 번 나타난 숫자만 남음