[LeetCode] 238. Product of Array Except Self (C#)

https://leetcode.com/problems/product-of-array-except-self/

nums[i] 자신을 제외한 다른 모든 원소의 곱을 answer[i] 에 입력하여 반환하는 문제.

nums 배열 원소의 prefix product 값과 suffix product 값은 32bit 정수값이 되도록 주어진다.

 

제한사항

• 시간복잡도 O(n)
• 나눗셈 연산 사용 불가

 

 

1. 나눗셈 연산을 사용했을 때의 답안

• 결과가 0 이 되는 경우를 분리하여 코드를 구성
  • 한 번에 이해하기 어려운 조건식
• list 배열을 사용하여 불필요한 Array 변환 과정이 있음

public class Solution {
    public int[] ProductExceptSelf(int[] nums)
    {
        var productAll = 1;
        var zeroNumCnt = 0;

        foreach (var num in nums)
        {
            if (num is 0)
            {
                zeroNumCnt++;
                continue;
            }

            productAll *= num;
        }

        // except case.
        if (zeroNumCnt > 1)
        {
            return new int[nums.Length];
        }

        // normal case.
        var result = new List<int>();
        foreach (var num in nums)
        {
            if (num is 0)
            {
                result.Add(productAll);
            }
            else
            {
                if (zeroNumCnt == 1)
                {
                    result.Add(0);
                }
                else
                {
                    result.Add(productAll / num);
                }
            }
        }

        return result.ToArray();
    }
}

 

 

2. 나눗셈 연산을 사용하지 않는 답안

• i 번째 요소까지의 prefix 곱, suffix 곱을 배열로 저장하는 과정이 각각 필요함
• 결과는 prefix[i] * suffix[i] 연산 만으로 간결하게 구할 수 있음

public class Solution
{
    public int[] ProductExceptSelf(int[] nums)
    {
        var n = nums.Length;
        var prefix = new int[n];
        var suffix = new int[n];
        prefix[0] = 1;
        suffix[n - 1] = 1;

        for (var i = 1; i < n; i++)
        {
            prefix[i] = prefix[i - 1] * nums[i - 1];
        }
        
        for (var i = n - 2; i >= 0; i--)
        {
            suffix[i] = suffix[i + 1] * nums[i + 1];
        }

        var result = new int[n];
        for (var i = 0; i < n; i++)
        {
            result[i] = prefix[i] * suffix[i];
        }

        return result;
    }
}

 

 

3. 2번 답안의 확장 버전

suffix 또는 prefix 곱 중 하나만 저장하면 된다는 생각에서 착안된 풀이

• suffix 곱을 배열로 저장
• result[i] 를 구함과 동시에 prefix 곱을 계산
• 2번 답안보다 더 적은 반복 횟수와 적은 메모리 사용

public class Solution
{
    public int[] ProductExceptSelf(int[] nums)
    {
        var n = nums.Length;
        var suffixProduct = new int[n];
        var result = new int[n];

        var sp = 1;
        for (var i = n - 1; i >= 0; i--)
        {
            suffixProduct[i] = sp;
            sp *= nums[i];
        }

        sp = 1;
        for (var i = 0; i < n; i++)
        {
            result[i] = sp * suffixProduct[i];
            sp *= nums[i];
        }

        return result;
    }
}