LeetCode 268(Missing Number, Python)

1. 문제 링크

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

LeetCode - The World's Leading Online Programming Learning Platform

2. 문제 설명

• range[0,n] 사이의 숫자를 중복없이 포함하고 있는 nums라는 array가 주어졌을 때,
• range[0,n] 범위 해당 array에 빠진 숫자가 1개 있다고 할 때, 그 숫자를 반환하라. 
• 예시1)
  • nums = [3,0,1]
  • 이는 [0,1,2,3]에서 2가 빠졌음을 의미하므로 2를 반환한다.
• 예시2)
  • nums = [0,1]
  • 누락된 숫자가 리스트의 가장 오른쪽에 있을수도 있다.
  • 이 경우 2가 빠진 것이므로 2를 반환한다. 

3. 처음 풀이

• range[0,n]을 포함하고 있는 집합을 만들고, 주어진 nums를 집합으로 만든 뒤, 둘의 차집합의 원소를 pop하는 것으로 작성하였다. 
• 여기서 range[0,n]을 포함하고 있는 집합의 경우,
  • 한개가 누락된것이므로 nums의 길이 + 1만큼을 range하였다. (range(0,len(nums)+1)) 
• runtime은 90% 정도 나왔다.

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        return (set(range(0,len(nums)+1)) - set(nums)).pop()

 

4. 다른 풀이 

• 처음 풀이의 경우 O(n)의 공간복잡도와 O(n)의 시간복잡도를 가지고 있다. 
• 리트코드에서 Follow-up으로 O(1)만큼의 공간복잡도로 문제를 해결할 수 있는지 Follow-up question을 던졌는데,
• 아래처럼 상수 공간만 할당해서 공간복잡도 O(1)로 풀이하는 것도 가능했다. 
  • 1부터 n까지 숫자의 합을 구하는 공식은 n * (n+1) / 2 이다. 
  • 따라서, 1부터 n까지 숫자를 합한것과, nums자체를 합한것의 차이가, 실제 누락된 숫자가 됨을 알 수 있다. 

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