[Leetcode] 238. Product of Array Except Self

Identifying the Problem

자기 자신을 제외한 나머지 모든 곱을 수열로 리턴한다.

 

Input: nums = [1,2,3,4]

Output: [24,12,8,6]

Organizing thoughts

직관적인 방법으로 풀면 O(n²)로 금방 푼다.

하지만 어떤 문제를 풀든 O(n²) 보다 더 효율적으로 풀 수 있는 방법이 있다고 생각한다.

 

자세히 생각해 본 결과, 268 Missing number 문제의 알고리즘에서 해답을 얻었다. 

0~n까지 주어진 배열에서 빠진 숫자를 찾는 문제였다.

간단히 설명을 하면 0~n까지 다 더한 값과 수열을 다 더한 값을 뺏을 때 값이 답이었다.

게다가 0~n까지 다 더하는 과정은 등차수열 공식을 사용해 굳이 0~n 반복문을 하지 않아도 됐다.

 

[Leetcode] 268. Missing Number

각설하고 268번 문제의 아이디어를 그대로 따오면

 

1. 반복문으로 처음에 수열의 모든 값을 곱한다.

2. 그 다음 반복문에 모든 값을 곱한 값을 탐색 중인 수로 나눈다.

3. 나눈 값으로 탐색 중인 수열을 채운다.

 

하지만 nums = [-1,1,0,-3,3] 같은 경우는 index = 2에서
곱한 모든 값 / 0 = ? 으로 0으로 나누는 경우가 발생한다.

더 생각해보자

<수열 내 0이 1개인 경우>

0인 부분은 0이 아닌 수의 모든 곱을 넣으면 된다. 

0이 아닌 부분은 0을 넣으면 된다.

 

<수열 내 0이 2개인 경우>

모든 값이 0이 된다.

 

Sourcecode

int* productExceptSelf(int* nums, int numsSize, int* returnSize)
{
    int multi = 1;
    int count = 0; //0의 개수
    
    *returnSize = numsSize;
   
    for(int i=0;i<numsSize ; i++)
    {        
        if(nums[i] !=0)
            multi *= nums[i];
        else 
            count ++;
    }
    
    for(int i=0;i<numsSize; i++)
    {   
        if(nums[i] !=0 && count ==0) //0이 없는 경우
            nums[i] = multi / nums[i];
        else if(nums[i] ==0 && count == 1) //0이 1개이고 0인경우
            nums[i] = multi;
        
        
        else //0이 2개 이상인 경우혹은 1개인데 0이 아닌 경우
            nums[i] = 0;
        

     }
    
    return nums;  
}

Mistake

신나게 다 짜 놓고 이 부분을 고려를 안 했다.