[leetCode] 2348. Number of Zero-Filled Subarrays (Python) (feat.ChatGPT)

코딩 1일 1문제! 오늘의 문제는 leetCode 의 Number of Zero-Filed Subarrays 입니다.

Number of Zero-Filled Subarrays - LeetCode

👨🏻‍💻 문제 풀이 - SOMJANG

정답은 0 이 연속으로 나온 길이 ( n ) 들의 1 부터 n 까지의 합들을 모두 더한 값이 정답입니다.

이에 연속으로 0 이 나온 길이 ( n ) 들을 구하고 이들의 n * ( n + 1 ) // 2 를 계속 정답에 더해주면 됩니다.

👨🏻‍💻 코드 ( Solution ) - SOMJANG

class Solution:
    def zeroFilledSubarray(self, nums: List[int]) -> int:
        answer, zero_length = 0, 0

        last_idx = len(nums) - 1

        for num_idx, num in enumerate(nums):
            if num == 0:
                zero_length += 1
            elif num != 0 and zero_length != 0:
                answer += zero_length * (zero_length+1) // 2
                zero_length = 0
        else:
            if zero_length != 0:
                answer += zero_length * (zero_length+1) // 2
        
        return answer

👨🏻‍💻 코드 ( Solution ) - ChatGPT - 1회차 list out of range 에러 발생

class Solution:
    def zeroFilledSubarray(self, nums: List[int]) -> int:
        count = 0
        left, zeros = 0, 0
        for right in range(len(nums)):
            if nums[right] == 0:
                zeros += 1
            while zeros > right - left:
                if nums[left] == 0:
                    zeros -= 1
                left += 1
            count += right - left + 1 - zeros
        return count

첫째로 받은 코드는 list out of range 에러가 발생하여 너무 아쉬웠습니다.

👨🏻‍💻 코드 ( Solution ) - ChatGPT - 2회차  -  SOMJANG 코드와 거의 일치

class Solution:
    def zeroFilledSubarray(self, nums: List[int]) -> int:
        count = 0
        window_size = 0

        for num in nums:
            if num == 0:
                window_size += 1
            else:
                count += window_size * (window_size + 1) // 2
                window_size = 0

        if window_size > 0:
            count += window_size * (window_size + 1) // 2

        return count

다시 요청해서 받은 코드는

제가 문제를 풀때 사용했던 for - else 구문이 for 가 끝난 뒤에 if 로 체크하는 것 말고는

변수명만 다른 코드였습니다.

👨🏻‍💻 코드 ( Solution ) - ChatGPT - 3회차  -  최적화 요청 코드 - 오류는 나지 않지만 틀린 답

class Solution:
    def zeroFilledSubarray(self, nums: List[int]) -> int:
        count = 0
        left = 0

        for right in range(len(nums)):
            if nums[right] == 0:
                count += (right - left + 1) * (right - left) // 2
            else:
                left = right + 1

        return count

그럼 이제 성능과 메모리 사용량 방면으로 최적화를 부탁했더니 코드를 아주 슥슥 작성하길래

오... 역시 인가! 했는데

위 코드를 제출하여보니 에러가 발생하여 너무 아쉬웠습니다.

이후 여러차례 더 좋은 성능의 코드를 작성해달라고 요청하였으나

더 나은 성능과 더 적은 메모리 사용량의 코드는 볼 수 없었습니다....

 

GitHub - SOMJANG/CODINGTEST_PRACTICE: 1일 1문제 since 2020.02.07