LeetCode [268]: Missing Number

📌 LeetCode [268]: Missing Number

🔗 문제 링크

---

문제 설명 📄

0부터 n까지의 숫자가 포함된 배열 nums가 주어집니다. 배열에서 하나의 숫자가 누락되어 있을 때, 이 누락된 숫자를 반환하는 문제입니다.

---

문제 접근 방식 📋

1. 숫자 포함 여부 확인:
   • 주어진 숫자들을 집합으로 저장하고, 0부터 n까지 모든 숫자를 확인하여 누락된 숫자를 반환합니다.
2. 리팩토링 아이디어:
   • 합 공식을 활용하여 0부터 n까지의 합과 실제 배열의 합을 계산한 뒤, 두 합의 차이를 반환하여 누락된 숫자를 찾습니다.
   • 이 방식은 시간 복잡도가 낮고, 추가 공간이 필요하지 않습니다.

---

Solution 💻

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        pattern = {i for i in nums}

        for i in range(len(nums) + 1):
            if i not in pattern:
                return i

시간 복잡도 분석 ⏲️

• 시간 복잡도: O(n)
  • 숫자를 집합으로 변환하는 데 O(n) 시간이 소요되며, 각 숫자를 탐색하는 데도 최대 O(n)이 소요됩니다.
• 공간 복잡도: O(n)
  • 집합에 모든 숫자를 저장하는 데 추가 공간이 필요합니다.

---

리팩토링 🛠️

개선된 코드 (합 공식 이용)

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        n = len(nums)

        expected_sum = n * (n + 1) // 2
        actual_sum = sum(nums)

        return expected_sum - actual_sum

리팩토링 코드의 차이점

1. 공간 효율성 개선:
   • 집합을 사용하지 않고, 합 공식을 사용하여 추가 공간을 제거했습니다.
2. 직관적인 접근:
   • 합 공식을 활용한 방식은 간결하고 계산 비용이 적습니다.

시간 복잡도 분석 ⏲️

• 시간 복잡도: O(n)
  • 배열을 한 번 순회하여 합을 계산합니다.
• 공간 복잡도: O(1)
  • 추가 공간을 사용하지 않습니다.

---