리트코드 - 238. Product of Array Except Self

리트코드 - 238. Product of Array Except Self

출처 - https://leetcode.com/problems/product-of-array-except-self/?envType=study-plan-v2&envId=top-interview-150

 

문제 설명

정수 배열 nums가 주어지면 answer[i]가 nums[i]를 제외한 nums의 모든 요소의 곱과 같은 배열 answer를 반환합니다.
nums의 접두사나 접미사의 곱은 32비트 정수에 들어가는 것이 보장됩니다.
나눗셈 연산을 사용하지 않고 O(n) 시간에 실행되는 알고리즘을 작성해야 합니다.

 

의사코드

int[] answer = new int[nums.length] answer[0] = 1 leftSum = 1 반복문 시작 (i = 1부터 1씩 증가, i < nums.length까지)     answer[i] *= leftSum     leftSum *= nums[i] 반복문 종료 rightSum = 1 반복문 시작: (i = nums.length - 1부터 1씩 감소, i >= 0까지)     answer[i] *= rightSum     rightSum *= nums[i] 반복문 종료 answer 리턴

 

풀이코드

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

        int leftSum = 1;
        for (int i = 0; i < n; i++) {
            answer[i] = leftSum;
            leftSum *= nums[i];
        }

        int rightSum = 1;
        for (int i = n - 1; i >= 0; i--) {
            answer[i] *= rightSum;
            rightSum *= nums[i];
        }

        return answer;
    }
}

 

코드설명

나눗셈을 사용하지 않고, O(n) 시간에 배열 곱셈을 구해야 한다.

배열을 반복문을 돌리고 안에서 다른 배열들을 O(n^2) 시간이 걸리므로 다른 방법을 생각해봐야 한다.

 

문제에서 자기 자신을 제외하고 곱셈을 구하는 것이므로

자기자신을 제외하고 왼쪽과 오른쪽 곱을 구한다음 그걸 다시 곱하면 된다.

 

즉, 첫번째 반복문을 돌 때에는 왼쪽 배열들의 곱한 값을 저장한다.

두번째 반복문을 돌 때에는 오른쪽 배열들의 곱한 값을 저장한다.

 

먼저 answer 배열을 하나 만들고 leftSum에 1을 넣어준다.

이렇게 하는 이유는 0번째 배열 왼쪽에는 아무값도 없기 때문에 초기값을 세팅하기 위함이다.

 

첫번째 반복문에서 answer배열에 leftSum을 대입하고, leftSum에 nums배열의 i번째를 곱해준다.

이렇게 하면 배열을 돌 때 자신 기준 왼쪽의 곱들이 저장된다.

 

예를 들어 nums = [1,2,3,4] 라면, answer가 첫번째 반복문을 돌면 answer = [1,1,2,6]이 될 것이다.

 

두번째 반복문에서도 똑같이 rightSum = 1 로 만들어 우선 이 값을 answer 배열 마지막에 곱해주고,

rightSum에다가 nums[i] 번째 배열의 값을 곱해주는 것을 순회하면 된다.

 

이렇게 하면 answer = [1,1,2,6] 배열이 answer = [24,12,8,6] 이 될 것이다.

 

시간복잡도 - O(n)

공간복잡도 - O(1)

 

문제를 풀며 생각한 흐름과 배운 점

초기코드

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] leftMul = new int[n];
        int[] rightMul = new int[n];
        Arrays.fill(leftMul, 1);
        Arrays.fill(rightMul, 1);
        int sum = 1;
        for (int i = 1; i < n; i++) {
            sum *= nums[i - 1];
            leftMul[i] *= sum;
        }
        sum = 1;
        for (int i = n - 2; i >= 0; i--) {
            sum *= nums[i + 1];
            rightMul[i] *= sum;
        }
        for (int i = 0; i < n; i++) {
            leftMul[i] *= rightMul[i];
        }
        return leftMul;
    }
}

초기에 생각한 코드는 위와 같다.

두 개의 배열을 사용했는데 런타임이 3ms가 나와서 배열을 하나로 줄여봤다.

 

리팩토링

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

        for (int i = 1; i < nums.length; i++) {
            answer[i] = answer[i - 1] * nums[i - 1];
        }
        int sum = 1;
        for (int i = nums.length - 1; i >= 0; i--) {
            answer[i] *= sum;
            sum *= nums[i];
        }

        return answer;
    }

오른쪽 배열을 순회할 때 sum을 사용하다가 left도 똑같이 사용하면 어떨까 싶어 풀이코드처럼 적용하게 되었다.

 

정리

배열을 쪼개서 순회하는 방법