[Grind75-LeetCode] Product of Array Except Self JAVA

반응형

728x90

[Grind75-LeetCode] Product of Array Except Self - Medium

---

접근

• 누적곱

---

풀이

주어지는 정수 배열에서 각 인덱스 값을 제외한 나머지 값의 곱을 배열 형태로 반환하는 문제이다. 2중 for문을 사용해 현재 인덱스를 제외한 나머지를 곱하면 되는 간단한 문제이지만 조건으로 O(n)의 시간 복잡도를 만족하는 코드를 제출해야 하기에 다른 방법을 선택해야 한다. 비슷한 형태의 값을 더하는 문제에서 사용했던 누적합 방식을 곱하기로 가능한지 찾아봤다. 당연하게도 누적곱 방식이 존재했고 이 문제는 누적곱 방식으로 O(n) 시간 복잡도를 만족하며 풀 수 있다.

 

누적곱이란 배열의 요소를 순차적으로 곱해나가는 방식이다. 누적곱을 만드는 방식은 누적곱 배열의 인덱스에 들어있는 값과 원본 배열의 값을 곱하여 다음 인덱스에 넣는 형태로 진행된다. 누적곱 배열의 첫 인덱스는 곱하기를 위해 1로 초기화되고 누적곱 0번 인덱스에 들어있는 값 1과 원본 배열 0번 인덱스 값이 곱해져 누적곱 배열 1번 인덱스에 들어가게 된다.

원본 배열 = [1, 2, 3, 4] 누적곱 배열 = [0, 0, 0, 0]

i = 0
누적곱[0] = 1
원본 배열 = [1, 2, 3, 4] 누적곱 배열 = [1, 0, 0, 0]

i = 1
누적곱[1] = 누적곱[0] * 원본[0] = 1 * 1 = 1
원본 배열 = [1, 2, 3, 4] 누적곱 배열 = [1, 1, 0, 0]

i = 2
누적곱[2] = 누적곱[1] * 원본[1] = 1 * 2 = 2
원본 배열 = [1, 2, 3, 4] 누적곱 배열 = [1, 1, 2, 0]

i = 3
누적곱[3] = 누적곱[2] * 원본[2] = 2 * 3 = 6
원본 배열 = [1, 2, 3, 4] 누적곱 배열 = [1, 1, 2, 6]

왼쪽에서 오른쪽으로 누적곱을 구하는 과정이다. 누적곱 배열이 만들어진 모습을 보면 한 가지 알 수 있는 점이 있다. 누적곱 인덱스의 값은 원본 배열의 해당 인덱스 값을 제외한 왼쪽 요소들을 곱한 값과 같다. 누적곱[3]의 값은 원본 배열[0] ~ [2]의 요소들을 곱한 것과 같기에 문제에서 요구한 절반은 이미 완성한 셈이다. 만약 배열이 6번 인덱스까지 존재한다면 [4]~[6]에 해당하는 값들의 곱만 추가로 곱해주면 된다. 

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

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

우선 왼쪽에서 오른쪽으로 누적곱을 구하는 코드이다. 단순히 answer [0]을 1로 초기화하고 answer [i] = answer [i-1] * nums [i-1]을 해도 되지만 뒤에 나올 코드와 동일하게 맞추기 위해 누적곱을 저장하는 변수를 따로 두었다. 0번 인덱스는 알아서 누적곱 변수의 초기값 1로 할당이 되고 누적곱 변수에 원본 배열의 값이 곱해진 뒤 다음으로 넘어간다. 그리고 구해졌던 누적곱이 배열의 다음 인덱스에 할당되고 다시 원본 배열 값이 곱해지고 넘어가는 방식으로 진행된다. 

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

        return answer;
    }

나머지 절반의 코드이다. 왼쪽에서 오른쪽으로 누적곱을 구하는 코드만 수행할 경우 해당 인덱스의 오른쪽에 있는 요소 값이 곱해지지 않기 때문에 오른쪽에서 왼쪽으로 누적곱을 한 번 더 진행해 주면 인덱스 값을 제외한 나머지 요소들의 곱이 구해지게 된다. 이미 누적곱 배열에 값이 들어있는 상태이기 때문에 2번째 for문에선 answer [i] = answer [i+1] * nums [i+1] 형태의 식을 사용하지 못하기 때문에 누적을 변수를 두어 따로 빼주는 것이다. 

누적곱

이 문제도 성능이 왔다 갔다 한다. 실행 시간이 1ms와 2ms를 제출할 때마다 왔다 갔다 한다.

---

나눗셈을 이용한 방식

실행 시간이 나와있는 그래프를 누르면 해당 실행 시간으로 제출되었던 코드를 볼 수 있다는 걸 이 문제를 풀면서 알았다. 이때까지 solutions 탭을 돌아다니며 코드를 찾아봤었는데 이렇게 간단한 방법이 있었다. 그래서 0ms의 실행 시간은 어떤 코드인지 살펴봤더니 똑같은 누적곱 방식인데 static으로 해당 문제의 메서드를 500번 실행시키는 코드가 들어있었는데 {0,0} 배열을 파라미터로 넘겨 500번 실행시키며 평균 실행 시간을 단축시키는 꼼수를 사용한 코드인 거 같았다. 그런 방식으로 실행 시간을 단축시킬 생각을 했다는 것도 신기했고 코드 자체는 동일했기 때문에 1ms 실행 시간을 가진 나눗셈을 이용하여 푼 코드를 가져왔다. 제출된 샘플 코드라고 떠 있어 누가 제출한 건진 알 수 없었다. 

public int[] productExceptSelf(int[] nums) {
        int max = 1; 
        boolean hasZero = false; 
        boolean hasMoreZero = false; 

        for (int n : nums) {
            if (n != 0) {
                max = max * n; 
            } else {
                if (hasZero) {
                    hasMoreZero = true;
                }
                hasZero = true; 
            }
        }

이 코드의 핵심은 0의 개수를 세는 것과 모든 요소를 곱한 뒤 해당 인덱스 값을 나눠 제외시켜 주는 것이었다. 우선 모든 요소의 곱을 저장할 변수와 0의 개수를 세기 위한 변수를 선언했다. 루프를 돌며 0이 아닐 경우 max 변수에 값을 곱해준다. 0이 나오는 경우 hasZero 변수와 hasMoreZero 변수를 사용해 0의 개수를 체크해 주는데 0 이 두 개 이상 나온다면 어차피 모든 요소의 곱은 0이 되기 때문이다. hasMoreZero로 두 번째 0이 발견되면 더 이상 진행이 의미가 없기 때문에 break를 해줘도 좋을 거 같다. 

	if (hasMoreZero) {
            for (int i = 0 ; i < nums.length; i++) {
                nums[i] = 0;
            }
            return nums;
        }

        for (int i = 0 ; i < nums.length; i++) {
            if (hasZero) {
                if (nums[i] != 0) {
                    nums[i] = 0;
                } else {
                    nums[i] = max;
                }
            } else {
                nums[i] = max / nums[i];
            }
        }
        
        return nums;
    }

hasMoreZero가 true인 경우 0이 두 개 이상이라는 뜻으로 배열의 모든 인덱스를 0으로 채워 반환한다. 0이 한 개이거나 존재하지 않는 경우 배열을 채우게 되는데 0이 존재한다면 해당 인덱스의 값이 0이 아닌 부분은 모두 0이 곱해져 0이 되므로 0으로 채우고 인덱스 값이 0인 곳은 자신의 값 0을 제외한 나머지 요소들의 곱이기 때문에 max에 들어있는 값을 할당해 준다. 그리고 0이 존재하지 않는 경우 모든 요소의 곱인 max를 각 인덱스 값으로 나눠 제외시킨 뒤 반환한다. 

 

이 방법 또한 for문 2번 반복으로 누적곱과 동일하게 1ms~2ms 실행 시간으로 수행되는 코드이다. 

---

전체 코드

누적곱

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

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

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

        return answer;
    }
}

 

나눗셈

class Solution {
    public int[] productExceptSelf(int[] nums) {
        
        int max = 1;
        boolean hasZero = false;
        boolean hasMoreZero = false;

        for (int n : nums) {
            if (n != 0) {
                max = max * n; 
            } else {
                if (hasZero) {
                    hasMoreZero = true;
                    break;
                }
                hasZero = true;
            }
        }

        if (hasMoreZero) {
            for (int i = 0 ; i < nums.length; i++) {
                nums[i] = 0;
            }
            return nums;
        }

        for (int i = 0 ; i < nums.length; i++) {
            if (hasZero) {
                if (nums[i] != 0) {
                    nums[i] = 0;
                } else {
                    nums[i] = max;
                }
            } else {
                nums[i] = max / nums[i];
            }
        }
        
        return nums;
    }
}