Python으로 푸는 LeetCode 268. Missing Number (Easy)

이 문제는 0, 1, 2....n으로 이루어진 숫자들을 원소로하는 리스트에서,

빠진 숫자가 무엇인지를 찾아 반환할 수 있도록 코드를 짜야한다.

LeetCode에서 푼 문제 리스트 보기

LeetCode에서 문제 보기

Github에서 코드 보기

문제 풀이

n까지의 숫자의 총합은 계산하였을 때, n(n+1)/2 이다. 이 식을 이용하여 총합에서 list의 모든 값을 더한 값을 뺐을 때, 빠진 숫자를 찾을 수 있다. 단, 총합에서 list의 모든 값을 더한 값을 뺐을 때읙 결과 값이 0인 경우는 예외처리해주어야 한다.

리스트 내에 0이 있을 경우,  리스트에서 빠진 숫자는 가장 큰 값인 n이므로 리스트이 최대값에서 1을 더한 숫자를 반환하여야 한다.

리스트 내에 0이 없을 경우, 리스트에서 빠진 숫자는 0이므로 0을 반환해주어야 한다.

파이썬 코드

class Solution:
    def missingNumber(self, nums) -> int:
        """
        Runtime : faster than 33.94% of Python3
        Memory Usage : less than 5.25% of Python3
        """
        max_v = 0
        total = 0
        isinZero = False
 
        for n in nums:
            if n == 0:
                isinZero = True
            total += n
            max_v = max(max_v, n)
 
        if not isinZero:
            return 0
 
        result = int(max_v*(max_v + 1)/2 - total)
 
        if result == 0:
            return max_v + 1
 
        return result