Missing Number

문제 링크

https://leetcode.com/problems/missing-number/

문제 설명

정수 배열 nums가 주어졌을 때, 0부터 n까지의 숫자 중 배열에 없는 유일한 숫자를 찾는 함수를 작성하세요. 여기서 n은 배열의 길이이며, nums에는 [0, n] 범위의 숫자가 중복 없이 포함되어 있습니다.

입력: 배열 nums (길이 n)
출력: 0부터 n까지의 숫자 중 nums에 없는 숫자

예제

예제 1
- 입력: nums = [3, 0, 1]
- 출력: 2
- 설명: n = 3이므로 [0, 3] 범위의 숫자는 0, 1, 2, 3입니다. 이 중 2가 배열에 없으므로 2를 반환합니다.
예제 2
- 입력: nums = [0, 1]
- 출력: 2
- 설명: n = 2이므로 [0, 2] 범위의 숫자는 0, 1, 2입니다. 2가 배열에 없으므로 2를 반환합니다.
예제 3
- 입력: nums = [9, 6, 4, 2, 3, 5, 7, 0, 1]
- 출력: 8
- 설명: n = 9이므로 [0, 9] 범위의 숫자는 0부터 9까지입니다. 8이 배열에 없으므로 8을 반환합니다.

풀이 전략

이 문제는 0부터 n까지의 모든 숫자 중 nums에 없는 숫자를 찾는 문제입니다. 다음과 같은 여러 가지 방법을 사용할 수 있습니다.

합을 이용한 수학적 접근:
- 0부터 n까지의 숫자의 합은 (\text{total_sum} = \frac{n \times (n + 1)}{2})로 계산할 수 있습니다.
- nums 배열의 모든 숫자를 더한 값을 array_sum이라 하면, total_sum - array_sum이 배열에 없는 숫자가 됩니다.
- 시간 복잡도는 (O(n)), 공간 복잡도는 (O(1))입니다.
비트 연산을 이용한 접근:
- 모든 숫자를 XOR 연산으로 결합하면 중복된 숫자들이 상쇄되므로, 최종 결과는 없는 숫자만 남습니다.
- 예를 들어 0 ^ 1 ^ 2 ^ ... ^ n과 nums의 모든 숫자를 XOR 연산하여 결과를 얻을 수 있습니다.
- 시간 복잡도는 (O(n)), 공간 복잡도는 (O(1))입니다.

코드 분석

방법 1: 합을 이용한 수학적 접근

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        n = len(nums)
        total_sum = n * (n + 1) // 2  # 0부터 n까지의 숫자의 합
        array_sum = sum(nums)  # 배열의 합
        return total_sum - array_sum  # 차이를 반환

동작 원리:
- total_sum은 0부터 n까지 모든 숫자의 합입니다.
- array_sum은 nums 배열에 포함된 숫자들의 합입니다.
- total_sum - array_sum을 계산하면 배열에 없는 숫자를 얻을 수 있습니다.
시간 복잡도: (O(n)), 리스트 nums의 합을 계산하는 데 O(n) 시간이 소요됩니다.
공간 복잡도: (O(1)), 추가 메모리를 거의 사용하지 않습니다.

방법 2: 비트 연산을 이용한 접근

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        n = len(nums)
        missing = n  # 시작 값으로 n을 설정
        for i in range(n):
            missing ^= i ^ nums[i]  # i와 nums[i]의 값을 XOR
        return missing

동작 원리:
- 0 ^ 1 ^ 2 ^ ... ^ n과 nums의 모든 숫자를 XOR 연산하면 중복된 숫자가 상쇄되어 배열에 없는 숫자만 남습니다.
- missing을 n으로 초기화한 후, i와 nums[i]를 XOR 연산하여 결과를 계속 누적합니다.
- 최종적으로 missing에는 배열에 없는 숫자만 남습니다.
시간 복잡도: (O(n)), 리스트를 한 번 순회하므로 O(n)입니다.
공간 복잡도: (O(1)), 추가 메모리를 거의 사용하지 않습니다.

요약

합을 이용한 수학적 접근은 간단하며 빠르게 계산할 수 있습니다.
비트 연산 접근은 XOR을 활용하여 배열을 상쇄하는 방법으로, 코드가 간결하고 효율적입니다.

두 방법 모두 시간 복잡도 (O(n)), 공간 복잡도 (O(1))의 효율적인 풀이입니다.