[자바 알고리즘 인터뷰] 7장 배열(5) 자신을 제외한 배열의 곱

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

 
 
- 배열을 입력받아 output[i]가 자신을 제외한 나머지 모든 엘리먼트의 곱셈 결과가 되도록 출력하라 
- 나눗셈을 하지 않고 O(n)에 풀이 
 
 

풀이 1) 왼쪽 곱셈 결과에 오른쪽 값을 차례대로 곱하기 

 
 
- 나눗셈을 하지 않고 O(n)에 풀이하라는 조건이 있으므로 미리 전체 곱셈 값을 구해놓고 각 항목별로 자기 자신을 나눠서 풀이하는 방법은 안됨
- 가능한 풀이법은 자기 자신을 제외하고 왼쪽의 곱셈 결과와 오른쪽의 곱셈 결과를 곱하는 방법 
 
 

출처 : 자바 알고리즘 인터뷰 with 코틀린 저자: 박상길 <책만>

 
 
- 곱셈 결과는 p 변수에 저장하고 먼저 왼쪽부터 p에 곱해나간다. 
- 곱셈 결과는 그대로 정수형 배열 result[]에 담기며, 마지막 값 곱셈 값을 제외하며 result의 값은 [1,1,3,15]가 된다. 

//왼쪽 곱셈
int p = 1;
for(int i=0; i<nums.length; i++)
{
   result[i] = p;
   //왼쪽 곱셈 결과 
   p*=nums[i];
}

 
 
- 기존 result 변수를 재활용하여 반대로 오른쪽에서 곱한 결과를 넣어본다.
- 왼쪽의 곱셈 결과에 오른쪽 마지막 값부터 차례대로 곱한다. 

//오른쪽 곱셈, 왼쪽 곱셈 결과에 차례대로 곱하기 
p=1;
for(int i=nums.length-1; i>=0; i--)
{
    result[i] *=p;
    //오른쪽 곱셈 결과 
    p*=nums[i];
}

 
- 여기서 p는 1부터 시작해 차례대로 오른쪽 곱셈 결과로 1,7,35,105가 되고  최종적으로 이 값이 왼쪽 곱셈 결과에 뒤부터 곱해지면서 result 변수에는 정답인 [105,35,21,15]가 담긴다. 
 
 

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int result[] = new int[nums.length];

        //왼쪽 곱셈
        int p = 1;
        for(int i=0; i<nums.length; i++)
        {
            result[i] = p;
            //왼쪽 곱셈 결과 
            p*=nums[i];
        }

        //오른쪽 곱셈, 왼쪽 곱셈 결과에 차례대로 곱하기 
        p=1;
        for(int i=nums.length-1; i>=0; i--)
        {
            result[i] *=p;
            //오른쪽 곱셈 결과 
            p*=nums[i];
        }

        return result;
    }
}

 
실행시간 : 2밀리초