LeetCode 137(Single Number II, Python)

1. 문제 링크

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

Single Number II - LeetCode

 

2. 문제 설명

• 정수로 구성된 array nums가 주어졌을 때, 한 개의 element를 제외하고는, 모두 3번씩 등장한다고 할 때,
• 3번 등장하지 않은 element를 찾아서 반환
• 예시1) nums = [2,2,3,2]이면, 3만 한 번 등장했으므로, 3을 반환
• 예시2) nums = [0,1,0,1,0,1,99]이면, 99만 한 번 등장했으므로, 99를 반환
• 여기서 중요한 점은, linear runtime complexity를 가져야 하고, 오직 상수 공간만 사용할 수 있다는 제한이다. (runtime compexity O(N), space complexity O(1)이 되는 것)

3. 처음 풀이

• O(1)의 공간복잡도로 푸는 것은 결국 떠올리지 못했고,
• dictionary에 hist를 저장하면서 만약 value가 3이 아니면, 해당 값을 return하는 방식으로 해결했다.
• 그래도 leetcode runtime은 나쁘지 않았고, 다른 분들 풀이도, 공간 복잡도 O(1)을 지키지 않은듯 했다. 

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

        history = {}

        for index,i in enumerate(nums):
            if i not in history:
                history[i] = 1
            else:
                history[i] +=1
        
        for i in history:
            if history[i] != 3:
                return i

 

4. 다른 풀이

• 그럼에도 가장 빠른 풀이는, 공간복잡도 O(1)을 갖는, 비트연산자를 활용한 풀이었다. 
• 비트연산자는 항상 먼저 풀이를 떠올리기가 참 어렵다. 

def singleNumber(nums):
    ones = 0
    twos = 0

    for num in nums:
        ones = (ones ^ num) & ~twos
        twos = (twos ^ num) & ~ones

    return ones

• 한번 나타난 비트 처리 (ones 변수 업데이트)
  • 현재 비트가 처음 나타났으면, ones에 해당 비트를 저장
  • 현재 비트가 이미 있었으면, ones에서 그 비트를 제거
• 두번 나타난 비트 처리 (twos 변수 업데이트)
  • 현재 비트가 처음 나타났으면, twos에 그 비트 저장
  • 현재 비트가 이미 나타났다면, twos에서 그 비트 제거
• 세번 이상 나타난 비트는, 
  • ones, twos 동시에 특정 비트가 설정되있으면, 해당 비트가 세번 이상 나타났다는 것으로, 해당 비트 제거하여 초기화
• 결과적으로 ones 변수에는 한 번 나타난 비트만 남게 되므로, 모든 요소에 대해 반복한 뒤, ones를 리턴한다. 
• 이걸 어떻게 떠올리지.. 아직 직관적으로 이해가 안간다. 어려운 문제라 생각한다. 

 

5. 배운 점

• 비트 연산자. 익숙해지기