(Python3) - LeetCode (Easy) : 2996. Smallest Missing Integer Greater Than Sequential Prefix Sum

https://leetcode.com/problems/smallest-missing-integer-greater-than-sequential-prefix-sum

Smallest Missing Integer Greater Than Sequential Prefix Sum - LeetCode

간단 구현문제였습니다.

📕 풀이방법

📔 입력 및 초기화

📑 가장 긴 1씩 증가하는 순열의 누적합을 저장할 prefix_sum을 선언해 nums[0]에 저장합니다.

📔 풀이과정

📑 nums를 순회하며 가장 긴 1씩 증가하는 순열을 계산해 prefix_sum에 누적해 더해줍니다.

📑 조회를 위해 nums를 set로 바꿔 num_set에 저장합니다.
📑 num_set에서 prefix_sum이 없을때까지 1씩 증가시킵니다.

 

📑 시간 복잡도

O(N): nums에 대해 순회하기 때문입니다.

📑 공간 복잡도

O(N): nums 배열, nums 만큼의 set을 선언합니다.

📔 정답 출력 | 반환

최종 계산된 prefix_sum을 반환합니다.

---

📕 Code

📔 Python3

class Solution:
    def missingInteger(self, nums: List[int]) -> int:
        prefix_sum = nums[0]
        for i in range(1, len(nums)):
            if nums[i] != nums[i-1] + 1:
                break
            else:
                prefix_sum += nums[i]
        num_set = set(nums)
        while prefix_sum in num_set:
            prefix_sum += 1
        return prefix_sum

 

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.