[ leetcode 문제풀이 ] Maximum Product Subarray

https://leetcode.com/problems/maximum-product-subarray/

Maximum Product Subarray - LeetCode

(Maximum Product Subarray 문제는 위 링크에서 풀어보실 수 있습니다.)

 

 

 

< Maximum Product Subarray 문제 설명 >

 

Maximum Product Subarray 문제는 다음과 같다.

Given an integer array nums, find a contiguous non-empty subarray within the array that has the largest product, and return the product.

The test cases are generated so that the answer will fit in a 32-bit integer.

A subarray is a contiguous subsequence of the array.

 

주어진 nums 배열에 대해 가장 큰 곱을 나타내는 연속된 subarray를 찾아 그 곱을 리턴하여라. 

답은 32비트 정수에 맞도록 test case가 생성되고 subarray란 array의 연속된 부분수열이다.

 

다음 두 가지 출력 예시가 주어졌다.

 

주어진 제한 조건은 1 ≤ nums.length ≤ 2*10^4,  -10 ≤ nums[i] ≤ 10 과 nums의 어떠한 prefix, suffix product는 32비트 정수 값에 들어감을 보장한다는 것이다.

 

 

 

---

< Maximum Product Subarray 문제 접근 >

 

nums 배열의 원소는 정수 배열이다. 즉, 0이 아닌 그 어떤 값도 prefix product 하면 그 절댓값은 단조증가하게 된다. 따라서, 0을 기준으로 배열을 나누어 prefix product한 값을 구해오면 된다.

 

여기서 고려할 점은 절댓값은 항상 단조증가하지만 음수/양수도 고려해줘야 한다는 점이다. 따라서, 0을 기준으로 나눈 배열에 음수가 홀수개 들어있다면, 왼쪽에서 하나 뺀 subarray의 product와 오른쪽에서 하나 뺀 subarray의 product 값을 비교해보면 된다. 만약 음수가 짝수개 들어있다면, 배열 전체의 product 값이 max_product의 후보가 된다.

 

이 idea를 코드로 나타내면 다음과 같다. (Cpp 사용)

 

int maxProduct(vector<int>& nums) {
    int n = nums.size();
    if(n==1) return nums[0];
        
    int max_product = 0;  // n > 1인 경우 max_product의 최솟값은 0임
    int left = 0, right = 1; // left: 0 기준으로 나눈 영역의 맨 왼쪽 index
	                     // right: 영역을 탐색하는 역할
    
    vector<int> negativeIndex;
    if(nums[0] < 0) negativeIndex.push_back(0); // index 0에 대해 먼저 고려(while문때문)
    else if(nums[0] == 0) left = 1;
    
    while(right < n){
        while(right < n && nums[right] != 0){  // right로 영역 탐색
            if(nums[right] < 0)
                negativeIndex.push_back(right); // 음수 index 저장
            if(nums[right-1])  // nums[right]의 탐색(0, 음수값)을 방해하지 않도록 prefix product 동시 진행
                nums[right] = nums[right]*nums[right-1];  // prefix product 적용
            right++;
        } // while 문을 마치면 영역의 마지막+1의 위치를 가리킴(vec.end()와 같음)
            
        if(negativeIndex.size() & 1 && right-left > 1){ // 영역에 포함된 원소가 1개인 경우는 제외
            if(negativeIndex.back() > left) // negativeIndex.back()이 영역의 맨 왼쪽에 있는 경우 고려
                max_product = max(max_product, nums[negativeIndex.back()-1]);
            max_product = max(max_product, nums[right-1] / nums[negativeIndex.front()]);
        }
        else
            max_product = max(max_product, nums[right-1]);
            
        left = ++right;
        negativeIndex.clear();
    }
      
    return max_product;
}

 

여기서 detail한 처리로, 0의 위치를 기준으로 나눈 subarray의 원소가 1개인 경우(right-left = 1)와 배열에 음수 원소가 맨 왼쪽에 위치한 경우는 예외로 처리하였다. 

 

실행 결과 Runtime: 8 ms (faster than 65.89 %), Memory Usage: 13.9 MB (less than 10.40%)

 

 

 

---

< Another Solution >

 

다른 분들이 작성한 코드 중에 놀랍도록 간단한 코드를 발견해 정리해보려 한다.

 

int maxProduct(vector<int>& nums) {
    int n = nums.size();
    if(n == 1) return nums[0];
        
    int max_val = 1, min_val = 1;
    int max_product = 0;
    for(int i=0;i<n;i++){
        if(nums[i] < 0)
            swap(max_val, min_val);
        max_val = max(nums[i], max_val*nums[i]);
        min_val = min(nums[i], min_val*nums[i]);
        max_product = max(max_product, max_val);
    }
    return max_product;
}

 

원소들을 곱할수록 그 절댓값은 무조건 커짐을 max_val와 min_val 구하는 것으로 적용하였다. 

 

max_val을 update하는 max 연산에서 nums[i]가 선택되는 경우는 min_val이 양수인 상태에서 nums[i]가 음수인 경우, max_val = 0인 경우(nums[i-1]이 0인 경우)가 있고, min_val을 update하는 min 연산에서 nums[i]가 선택되는 경우는 min_val과 nums[i]가 양수인 경우, min_val = 0인 경우(nums[i-1]이 0인 경우)가 있다. 

 

즉, 배열에 0이 포함된 경우와 음수가 포함된 경우의 update를 자동적으로 처리하고 있는 것이다. 

 

for 문의 순회 과정에서 max_val과 min_val은 nums[0 .. i]의 subarray의 곱의 최댓값과 최솟값을 나타낸다. 이를 최종적으로 리턴하고자 하는 max_product에 업데이트해줌으로써 구하고자 하는 값을 얻는다.

 

 

내가 작성한 알고리즘과 비교를 해보면 max_product를 0이 있는 위치를 기준으로 나눠 계산하려 한 점에서는 동일하나 음수의 처리에서 확연한 차이를 보였다. 나는 최솟값에 대한 고려 없이 max_product를 구하려고 하다 보니 subarray에 포함된 음수의 갯수를 체크하는 등의 과정이 많이 필요했으나, 이 코드에서는 최솟값과 최댓값을 모두 구하다 보니 지저분한 조건문이 필요하지 않았다.

 

 

고생고생하면서 문제를 풀고 나서 이런 엄청나게 간단한 알고리즘을 마주하게 되면 엄청 힘빠진다...༎ຶ‿༎ຶ 

스스로의 부족함을 더욱 느끼게 되는 순간이다. 더 열심히 공부하자 (‘•̀ ▽ •́ )φ