Product of Array Except Self

[hsskey]

문제 설명 | Product of Array Except Self

정수 배열 nums가 주어질 때, 각 요소의 위치에 해당 요소를 제외한 모든 요소들의 곱을 담은 배열을 반환하는 문제

📝 제약조건

• 나눗셈 연산을 사용하지 않고 문제를 해결
• O(n) 시간 복잡도로 해결
• O(1) 추가 공간 복잡도로 해결

💡 예시

• Input: [1,2,3,4]
  • Output: [24,12,8,6]
  • 설명:
    • 1번 위치: 2 * 3 * 4 = 24
    • 2번 위치: 1 * 3 * 4 = 12
    • 3번 위치: 1 * 2 * 4 = 8
    • 4번 위치: 1 * 2 * 3 = 6

문제 해결 과정

Step 1: 문제 이해하기

• 작은 예시를 통해 이해하기

  • [1,2,3,4] → [24,12,8,6]
  • 각 위치의 값은 자신을 제외한 다른 모든 요소의 곱

• 제약사항 검토:

  • 나눗셈 없이 구현해야 함
  • O(N) 시간 복잡도 필요
  • O(1) 추가 공간 복잡도 필요

Step 2: 접근 방법

• 직관적으로 생각하기

  • 가장 단순한 방법은 이중 반복문을 사용하는 것이지만, 시간복잡도가 O(N²)
  • O(N)으로 해결하려면 배열을 한 번만 순회

• 문제 상황 단순화

  • 각 위치의 값은 "왼쪽 요소들의 곱" × "오른쪽 요소들의 곱"으로 생각
  • 예: [1,2,3,4]에서 3번째 위치(값 3)의 결과는 (1×2) × (4) = 8

• 알고리즘 표 구상

  1. 왼쪽에서 오른쪽으로 누적 곱 계산
     i = 0, prefix = 1
     ↓
     res[i] = prefix (현재 위치 왼쪽의 모든 요소 곱)
     ↓
     prefix *= nums[i] (다음 위치를 위한 누적 곱 업데이트)
     ↓
     i++ 하고 반복
     
  2. 오른쪽에서 왼쪽으로 누적 곱 계산
     i = n-1, postfix = 1
     ↓
     res[i] *= postfix (기존 값에 오른쪽 요소들의 곱 곱하기)
     ↓
     postfix *= nums[i] (다음 위치를 위한 누적 곱 업데이트)
     ↓
     i-- 하고 반복
  

Step 3: 코드 설계

1. 결과 배열 res 생성
2. 왼쪽에서 오른쪽으로 순회하며 왼쪽 누적 곱 저장
   • prefix 변수를 1로 초기화
   • 각 위치에 prefix 값 저장 후 prefix에 현재 값 곱하기
3. 오른쪽에서 왼쪽으로 순회하며 오른쪽 누적 곱 반영
   • postfix 변수를 1로 초기화
   • 각 위치의 값에 postfix 곱하기 후 postfix에 현재 값 곱하기
4. 결과 배열 반환

Step 4: 코드 구현

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var productExceptSelf = function(nums) {
    const res = Array(nums.length);
    
    // 왼쪽에서 오른쪽으로 누적 곱 계산
    let prefix = 1;
    for(let i = 0; i < nums.length; i++) {
        res[i] = prefix;
        prefix *= nums[i];
    }
    
    // 오른쪽에서 왼쪽으로 누적 곱 계산
    let postfix = 1;
    for(let i = nums.length - 1; i >= 0; i--) {
        res[i] *= postfix;  // 왼쪽 누적 곱에 오른쪽 누적 곱 곱하기
        postfix *= nums[i];
    }
    
    return res;
};

복잡도 분석

• 시간 복잡도: O(N) - 배열을 두 번 순회하지만 각각 O(N)이므로 총 복잡도는 O(N)
• 공간 복잡도: O(1) - 결과 배열 외 추가 배열 없이 변수만 사용

검증

• 예시 [1,2,3,4]로 실행해보기:
  1. 첫 번째 반복문 후: res = [1, 1, 2, 6]
  2. 두 번째 반복문 후: res = [24, 12, 8, 6]

[hsskey]

O(n^2) 풀이

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var productExceptSelf = function(nums) {
    const result = [];
    
    // 각 요소를 순회
    for(let i = 0; i < nums.length; i++) {
        let product = 1;
        
        // 현재 요소를 제외한 모든 요소의 곱 계산
        for(let j = 0; j < nums.length; j++) {
            // 현재 인덱스(i)는 건너뛰고 나머지 요소들을 곱함
            if(i !== j) {
                product *= nums[j];
            }
        }
        
        // 계산된 곱을 결과 배열에 추가
        result.push(product);
    }
    
    return result;
};