[LeetCode] 238. Product of Array Except Self

238. Product of Array Except Self

LeetCode

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

Product of Array Except Self - LeetCode

 

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
You must write an algorithm that runs in O(n) time and without using the division operation.

정수 배열 nums가 주어졌을 때, answer[i]가 nums[i]를 제외한 nums의 모든 원소의 곱과 같아지도록 하는 배열 answer를 반환하세요.
nums의 어떤 접두사(prefix)나 접미사(suffix)의 곱도 32비트 정수에 맞음이 보장됩니다.
여러분은 반드시 O(n) 시간 복잡도 내에 작동하고, 나눗셈 연산을 사용하지 않는 알고리즘을 작성해야 합니다.

 

Example

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

---

1. 문제 요구사항 분석

자기 자신만 빼고 나머지 모든 숫자를 곱한 값을 구하는 문제 

2. 접근 전략

😭 첫 번째 for문에서 다 곱한 후, 두 번째 for문에서 본인을 나누기 → 두 번째 예제와 같은 답이 나올 수 없음

😁 누적합 문제로 풀기

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] answer = new int[n];
        
        // 왼쪽 모든 원소들의 곱을 answer 배열에 누적
        answer[0] = 1;
        for (int i = 1; i < n; i++) {
            answer[i] = answer[i - 1] * nums[i - 1];
        }
        
        // 오른쪽에서부터 거꾸로 오면서 오른쪽 원소들의 곱을 구하고, 이미 answer에 저장된 왼쪽 곱과 바로 곱하기
        int rightProduct = 1;
        for (int i = n - 1; i >= 0; i--) {
            answer[i] = answer[i] * rightProduct; // (왼쪽 곱) * (오른쪽 곱)
            rightProduct *= nums[i];              // 다음 칸을 위해 현재 숫자를 누적
        }
        
        return answer;
    }
}

 

누적합 알고리즘이란

 

"그때그때 매번 더하지 말고, 미리 앞에서부터 더해둔 값을 이용해 빠르게 계산하자"는 전략

"어떤 배열이 주어졌을 때, 특정 구간(예: 3번째부터 7번째까지)의 합을 구해라."

 

❌ 누적합을 안 쓰면 생기는 문제

만약 배열의 길이가 10만 개인데, "X번부터 Y번까지 더해줘!"라는 요청을 10만 번 반복한다고 해볼게요. 요청이 올 때마다 일일이 for문을 돌려서 숫자를 더하면, 컴퓨터는 매번 엄청난 연산을 해야 해서 결국 시간 초과로 터지게 됩니다. (시간 복잡도: O(N×M))

 

⭕ 누적합을 쓰면 좋은 이유

미리 0번째부터 각 위치까지의 합을 미리 구해둔 배열을 하나 만들어 둡니다. 이렇게 준비해 두면, 아무리 긴 구간의 합을 구해달라고 요청해도 for문을 돌릴 필요 없이 단 한 번의 뺄셈으로 정답을 바로 찾아낼 수 있습니다! (시간 복잡도: O(1))

 

1단계: 누적합 배열(Prefix Sum Array) 만들기

원래 배열이 있으면, 앞에서부터 숫자를 누적해서 더한 새로운 배열 P를 만듭니다. 계산하기 편하게 보통 맨 앞에 0을 두고 시작하는 편이에요.

• 원래 배열: nums = [3, 5, 1, 4, 2]
• 누적합 배열 P 만들기:
  • P[0] = 0 (시작점)
  • P[1] = 0 + 3 = 3
  • P[2] = 3 + 5 = 8
  • P[3] = 8 + 1 = 9
  • P[4] = 9 + 4 = 13
  • P[5] = 13 + 2 = 15
• 결과: P = [0, 3, 8, 9, 13, 15]

2단계: 구간 합 공식 적용하기 (핵심!)

이제 문제에서 "인덱스 i부터 j까지의 합을 구해줘"라고 한다면, 공식은 아래 하나로 끝납니다.

구간 합=P[j+1]−P[i]

 

예를 들어, nums에서 1번째(5)부터 3번째(4)까지의 합(5 + 1 + 4 = 10)을 구하고 싶다면?

• P[4] (0~3번째까지의 총합 = 13) 에서
• P[1] (0번째까지의 총합 = 3) 을 뺍니다.
• 결과: 13 - 3 = 10