[Leetcode 아주 상세한 문제풀이] 268. Missing Number - 코드 line 별 설명

Leetcode 문제

이번에 풀어볼 문제는 리트코드 268번 문제 Missing Number 다.

우선 문제를 살펴보자.

 

리트코드 268번 문제 Missing Number 링크

Missing Number - LeetCode

Missing Number - LeetCode

 

 

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

 

Example 1:
Input: nums = [3,0,1]
Output: 2
Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.

Example 2:
Input: nums = [0,1]
Output: 2
Explanation: n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in the range since it does not appear in nums.

Example 3:
Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8
Explanation: n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 8 is the missing number in the range since it does not appear in nums.
 
Constraints:
n == nums.length
1 <= n <= 104
0 <= nums[i] <= n

 

 

문제 설명

문제를 간략히 살펴보자.

Range가 [0, n] 인 정수로 이루어진 배열이 주어진다.

이때 배열 안 모든 정수는 모두 다르다.

즉, n=3 이라면 0부터 3까지의 정수 배열 [0, 1, 2, 3] 이 주어진다.

따라서 위의 예시 1번에서 보는 것처럼 배열이 [3, 0, 1]로 주어진다면 배열에서 2가 빠진 것이기 때문에 2를 리턴해주면 된다.

문제가 매우 간단하기 때문에 곧바로 문제를 풀어보도록 하자.

 

 

문제 접근법

이 문제를 푸는 가장 간단한 방법은 우리가 초등학교 수학 시간에 배운 지식을 이용하는 것이다.

0부터 n까지의 모든 정수의 합에서 배열 안의 모든 정수의 합을 빼면 missing number를 쉽게 찾을 수 있다.

 

 

문제 풀이 1

곧바로 코드로 표현해 보자.

우선 배열을 입력받을 함수를 정의해 준다 (line 1)

그리고 배열 길이를 찾아낸다 (line 2)

우리가 알고 있는 지식에 의하면 1부터 n까지의 합은 n * (n + 1) / 2 로 표시된다 (line 3)

물론 0은 더해도 의미없다.

그리고 배열 안에 있는 모든 정수의 합을 구해준다 (line 4)

앞서 설명한 것처럼 0부터 n까지 합과 배열 안 정수들의 합의 차이가 바로 missing number가 된다 (line 5)

마지막에 그 missing number를 리턴해주면 된다.

참고로 이 알고리즘의 time complexity는 O (n)이다.

 

 

문제 풀이 코드 1

def missingNumber(nums):
    n = len(nums)
    expected_sum = n * (n + 1) // 2
    actual_sum = sum(nums)
    missing_number = expected_sum - actual_sum
    return missing_number
 
# Test cases
nums1 = [3, 0, 1]
print(missingNumber(nums1))  # Output: 2
 
nums2 = [0, 1]
print(missingNumber(nums2))  # Output: 2
 
nums3 = [9, 6, 4, 2, 3, 5, 7, 0, 1]
print(missingNumber(nums3))  # Output: 8
 

 

 

문제 풀이 코드 2

def missingNumber(nums):
    num_set = set(nums)
    n = len(nums)
    
    for i in range(n + 1):
        if i not in num_set:
            return i
 
# Test cases
nums1 = [3, 0, 1]
print(missingNumber(nums1))  # Output: 2
 
nums2 = [0, 1]
print(missingNumber(nums2))  # Output: 2
 
nums3 = [9, 6, 4, 2, 3, 5, 7, 0, 1]
print(missingNumber(nums3))  # Output: 8