LeetCode [136]: Single Number

📌 LeetCode [136]: Single Number

---

문제 설명 📄

주어진 정수 배열 nums에서, 모든 숫자가 두 번 나타나는 상황에서 단 한 번만 나타나는 숫자를 찾으세요.
반환 값은 반드시 고유하며, 배열의 각 요소는 한 번만 나타나거나 두 번 나타납니다.

---

문제 해결 접근 📋

1. 빈도 계산:
   • collections.Counter를 사용하여 각 숫자의 빈도를 계산합니다.
2. 단일 숫자 찾기:
   • 빈도 값이 1인 숫자를 찾아 반환합니다.

---

Solution 💻

from collections import Counter

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

        for key, value in count.items():
            if value == 1:
                return key

시간 복잡도 ⏲️

• 시간 복잡도: O(n)
  • Counter(nums)로 배열의 빈도를 계산 (O(n)).
  • 이후 순회하며 값이 1인 요소를 찾는 과정 (O(n)).

공간 복잡도 🗄️

• 공간 복잡도: O(n)
  • Counter를 사용하여 숫자의 빈도를 저장.

---

리팩토링 🛠️

개선된 코드

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        result = 0
        for num in nums:
            result ^= num
        return result

리팩토링 후 시간 복잡도 ⏲️

• 시간 복잡도: O(n)
  • 배열을 한 번 순회하며 XOR 연산.

리팩토링 후 공간 복잡도 🗄️

• 공간 복잡도: O(1)
  • 추가 메모리 사용 없이 단일 변수 result로 해결.