LeetCode 코딩테스트 Maximum Product Subarray – Array (6)

by

LeetCode는 소프트웨어 엔지니어링 및 코딩 인터뷰 준비를 위한 플랫폼이다. 다양한 프로그래밍 언어로 구현된 코딩 문제가 공하며 알고리즘 능력을 향상시키는데 도움을 준다.

LeetCode에 수 많은 문제 중에 시간을 절약하기 위해 New Year Gift – Curated List of Top 75 LeetCode Questions to Save Your Time 에서 각 카테고리/유형 별로 추천하는 75개 문제를 풀어본다.

이번 글에서는 Array문제인 Maximum Product Subarray 문제를 python으로 풀어보았다.

Leetcode 문제설명

이 문제는 정수 배열 nums가 주어졌을 때, 배열 내에서 부분배열의 곱 중에서 가장 큰 값을 찾고, 그 최대 곱을 반환하는 문제이다. 부분배열은 배열 내에서 연속된 원소들로 이루어진 것을 의미한다.

해당 문제는 ttps://leetcode.com/problems/maximum-product-subarray/ 에서 확인 할 수 있습니다.

예를 들어, 주어진 배열이 [2, 3, -2, 4]일 때, 이 배열에서의 부분배열 중 곱이 가장 큰 경우는 [2, 3]이며, 해당 부분배열의 곱은 6이다. 따라서 이 문제에서 함수는 6을 반환해야 한다.

제약사항은 다음과 같다.

배열의 길이는 최소 1이며 최대 2 * 10^4
배열의 각 원소는 -10에서 10까지의 정수
배열의 어떤 접두사(prefix)나 접미사(suffix)의 곱도 32비트 정수에 들어갈 수 있는 값으로 보장

솔루션

다음 코드는 이중 반복문을 사용하여 가능한 모든 부분배열의 곱을 계산하므로 시간 복잡도가 O(n^2)이다. 배열의 크기가 커질수록 실행 시간이 급격하게 증가하며, 효율성이 낮다.

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        # 입력 배열이 비어있으면 0을 반환
        if not nums:
            return 0

        # 배열의 길이를 구함
        n = len(nums)
        
        # 최대 곱을 음의 무한대로 초기화
        max_product = float('-inf')

        # 배열의 각 인덱스에 대해 반복
        for i in range(n):
            # 현재 부분배열의 곱을 저장하는 변수 초기화
            current_product = 1
            
            # 현재 인덱스 i에서 시작하여 배열의 끝까지 반복
            for j in range(i, n):
                # 현재 부분배열 곱에 현재 인덱스 j의 값을 곱함
                current_product *= nums[j]
                
                # 최대 곱을 현재 부분배열 곱과 기존 최대 곱 중 더 큰 값으로 갱신
                max_product = max(max_product, current_product)

        # 최종적으로 계산된 최대 부분배열 곱 반환
        return max_product
leetcode-Maximum-Product-Subarray-timelimit

다음 코드는 동적 프로그래밍의 아이디어를 활용하여 최대 연속 부분 배열 곱을 찾는다. 주요 알고리즘는 각 원소마다 최대값과 최소값을 유지하면서 순회하는 것이다. 음수가 등장할 경우 최대값과 최소값을 교환하는 이유는 음수가 하나 등장할 때 최대값과 최소값의 부호가 바뀌면서 절댓값이 커질 수 있기 때문이다.

이 알고리즘은 한 번의 순회로 해결되므로 시간 복잡도는 O(N)으로 보다 효율적으로 풀 수 있다.

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        # 입력이 빈 배열인 경우 0을 반환
        if not nums:
            return 0

        # 첫 번째 원소로 시작
        max_product = min_product = result = nums[0]

        # 배열의 두 번째 원소부터 순회
        for num in nums[1:]:
            # 현재 원소가 음수인 경우, 최대값과 최소값을 교환
            if num < 0:
                max_product, min_product = min_product, max_product

            # 최대값과 최소값 갱신
            max_product = max(num, max_product * num)
            min_product = min(num, min_product * num)

            # 현재까지의 최대값 갱신
            result = max(result, max_product)

        # 최종적으로 최대 연속 부분 배열 곱 반환
        return result

다음 문제는 Minimum in Rotated Sorted Array 입니다. 읽어주셔서 감사합니다.

LeetCode 코딩테스트 Minimum in Rotated Sorted Array – Array (7)

Leave a Comment