LeetCode DSA 시리즈 #6: 268. Missing Number

Source: Dev.to

문제 개요

이 문제는 LeetCode 268. Missing Number 로, nums 라는 배열에 [0, n] 범위에서 뽑힌 n개의 서로 다른 숫자가 들어있을 때, 배열에 없는 하나의 숫자를 찾는 것입니다.

문제 난이도는 Easy 로 분류됩니다.

접근법 1 – 집합 차집합

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

        # 전체 시퀀스 [0, n]을 만들고 집합으로 변환
        full_set = set(range(n + 1))

        # missing number는 full_set에 존재하지만 nums에는 없는 원소
        missing = full_set - set(nums)
        return missing.pop()

복잡도

• 시간: O(n) – 집합을 만들고 차집합을 구하는 과정에서 리스트를 한 번 스캔합니다.
• 공간: O(n) – 크기 n + 1인 추가 집합이 필요합니다.

접근법 2 – 완전 탐색

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

        # 0부터 n까지 각각 확인하고, nums에 없으면 반환
        for i in range(n + 1):
            if i not in nums:
                return i

복잡도

• 시간: 최악의 경우 O(n²) – i not in nums 가 매번 선형 탐색을 수행하기 때문입니다.
• 공간: O(1).

접근법 3 – 리스트 제거

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

        # 전체 리스트 [0, n]을 만든 뒤, nums에 있는 요소들을 차례로 제거
        sequence = list(range(n + 1))
        for num in nums:
            sequence.remove(num)
        return sequence[0]

복잡도

• 시간: O(n²) – list.remove 가 O(n)이고 이를 n번 호출합니다.
• 공간: O(n) – 보조 리스트 sequence가 필요합니다.

더 나은 해결법

1. XOR 방법 (시간 O(n), 공간 O(1))

같은 수와 XOR 하면 0이 되고, XOR 연산은 교환법칙이 성립합니다. 인덱스 0…n과 nums의 모든 원소를 XOR 하면 남는 값이 바로 누락된 숫자입니다.

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        missing = len(nums)          # n (추가 인덱스)으로 시작
        for i, num in enumerate(nums):
            missing ^= i ^ num
        return missing

복잡도

• 시간: O(n) – 한 번의 순회.
• 공간: O(1) – 몇 개의 정수 변수만 사용.

2. 합 공식 이용 (시간 O(n), 공간 O(1))

첫 n개의 자연수 합은 n*(n+1)//2 입니다. 전체 합에서 배열의 실제 합을 빼면 누락된 숫자를 얻을 수 있습니다.

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

복잡도

• 시간: O(n) – sum(nums) 를 계산하기 위해 한 번 순회.
• 공간: O(1).

XOR 방식과 합 공식 방식은 모두 집합 기반 방법보다 상수 계수 성능이 뛰어나면서도 선형 시간과 상수 추가 공간을 유지합니다.