[PS] Leet | 238. 자신을 제외한 곱

2025. 3. 18. 21:43·CS/PS

문제

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.

예시

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


Example 2

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

조건

  • 2 <= nums.length <= 105
  • -30 <= nums[i] <= 30
  • The input is generated such that answer[i] is guaranteed to fit in a 32-bit integer.

답

해당 인덱스를 기준으로 양 옆으로 숫자들을 구분해서 prefix products와 suffix products를 이용하여 해결합니다.

 

첫 루프에서는 prefix products만 구하고, 두 번째 루프에서 suffix products를 구해 prefix products와 곱합니다.

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int len = nums.size();
        std::vector<int> products(len, 1);
        int product_left = 1;
        int product_right = 1;

        for(int i=0; i<len; ++i) {
            products[i] = product_left;
            product_left *= nums[i];
        }
        for(int i=len-1; i>=0; --i) {
            products[i] *= product_right;
            product_right *= nums[i];
        }

        return products;
    }
};

 

시간복잡도 : O(n)

공간복잡도 : O(1)

728x90

'CS > PS' 카테고리의 다른 글

[PS] 가장 가까운 두 수  (0) 2025.03.21
[PS] Leet | 33. 정렬된 회전 배열에서의 탐색  (0) 2025.03.20
[PS] Leet | 153. 정렬된 회전배열에서의 최소값  (0) 2025.03.20
[PS] Leet | 152. 최댓값을 가지는 하위 배열 - 곱셈  (0) 2025.03.20
[PS] Leet | 53. 최댓값을 가지는 하위 배열 - 덧셈  (0) 2025.03.19
'CS/PS' 카테고리의 다른 글
  • [PS] Leet | 33. 정렬된 회전 배열에서의 탐색
  • [PS] Leet | 153. 정렬된 회전배열에서의 최소값
  • [PS] Leet | 152. 최댓값을 가지는 하위 배열 - 곱셈
  • [PS] Leet | 53. 최댓값을 가지는 하위 배열 - 덧셈
Rayi
Rayi
  • Rayi
    아카이브
    Rayi
  • 전체
    오늘
    어제
    • 분류 전체보기 (262)
      • CS (40)
        • ML (3)
        • CV (2)
        • PS (34)
      • Reveiw (17)
        • Paper (17)
        • Github (0)
      • Pytorch (5)
      • Language (58)
        • Python (7)
        • JavaScript (32)
        • TypeScript (16)
        • C++ (3)
      • IDE (12)
      • Git (13)
      • Frontend (71)
        • React (8)
        • SolidJS (20)
        • CSS (12)
      • UI (3)
      • Backend (15)
        • DB (17)
        • Node.js (11)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    UI
    frontend
    C++
    html
    CSS
    DB
    js
    CV
    ML
    CS
    postgresql
    deploy
    Git
    vscode
    ps
    API
    ts
    mongo
    Three
    react
    backend
    review
    SOLID
    figma
    python
    PRISMA
    PyTorch
    Express
    GAN
    nodejs
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.5
Rayi
[PS] Leet | 238. 자신을 제외한 곱
상단으로

티스토리툴바