[LeetCode] 238. Product of Array Except Self

date

‣

slug

leetcode-238

author

status

Public

문제 링크

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

문제

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements ofnums 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.

문제풀이

주어진 리스트에서 각 원소를 제외한 나머지 원소들의 곱으로 이루어진 새로운 리스트를 반환하는 문제입니다.

이 문제의 핵심 조건은 두 가지입니다:

나눗셈 없이 해결할 것 ➗❌

만약 나눗셈이 가능하다면, 모든 원소를 곱한 후 자기 자신으로 나누면 쉽게 해결할 수 있습니다.

시간 복잡도를 으로 유지할 것 ⏱️💨

만약 도 가능하다면, 단순히 두 번의 반복문으로 해결할 수 있습니다.

초기 아이디어 💡

처음 떠오른 아이디어는 문제의 조건을 확인하면서 생각해낸 것입니다. 여기서 "prefix"와 "suffix"라는 키워드를 보고 아이디어를 구상했습니다. 간단한 아이디어는 다음과 같습니다:

정방향 반복문으로 각 원소의 곱을 계산합니다. ➡️

역방향 반복문으로 마찬가지로 곱을 계산합니다. ⬅️

이를 통해 prefix와 suffix 리스트 두 개를 구할 수 있습니다.

구현 과정 🛠️

먼저 정방향 반복문을 살펴봅시다. 예시로 [1, 2, 3, 4] 리스트를 고려해보겠습니다.

prefix_dict에 값을 저장하며 진행합니다:

idx 0 → prefix_dict = {"0": 1}
idx 1 → prefix_dict = {"0": 1, "01": 2}
idx 2 → prefix_dict = {"0": 1, "01": 2, "012": 6}
마지막 원소는 건너뜁니다. ⛔

그다음은 역방향 반복문입니다:

[1, 2, 3, 4]의 경우:

idx 3 → suffix_dict = {"3": 4}
idx 1까지 진행합니다. 🔄

이렇게 구한 두 개의 dict를 합쳐서 최종 dict를 만들려고 했지만, 실제로 dict 형태로 합치는 데 어려움이 있었습니다. 그래서 각 prefix와 suffix를 리스트로 구한 후, 마지막 반복에서 이 둘을 합치려 했습니다. 🔗

최적화 과정 🚀

prefix와 suffix 리스트를 구한 후, zip을 사용해 순회하면서 합친 결과는 다음과 같았습니다:


result_dict = {"012": 6, "013": ..., "023": ..., "123": ...}

여기서 문제는 각 key와 value마다 값을 찾기 위해 의 시간 복잡도가 추가로 소요된다는 점이었습니다. 순차적으로 값을 구하기 때문에 적절한 순서로 정렬하면 추가 공간 없이도 순서대로 결과를 출력할 수 있을 것 같았습니다. ⏱️➡️

결국 prefix와 suffix를 따로 구하지 않고 바로 결과를 계산하는 방식으로 변경했습니다. 구체적으로는 다음과 같습니다:

result = [1 for _ in range(len(nums))]를 사용해 결과 리스트를 미리 초기화합니다. 📋

정방향 순회에서는 result[i+1]에 값을 곱해주고, 역방향 순회에서는 result[i-1]에 값을 곱해줍니다. ➡️⬅️

이렇게 하면 dict나 추가 공간을 사용하지 않고도 문제를 해결할 수 있었습니다. 👍

Follow-Up 문제 🔍

문제에서 제시한 Follow-up 조건은 다음과 같습니다:

Follow up: 나눗셈 없이 추가 공간 복잡도로 문제를 해결할 수 있나요? (결과 배열은 추가 공간으로 계산하지 않습니다.)

결과 리스트는 추가 공간으로 간주하지 않으므로, 현재의 cur_value 변수는 의 공간 복잡도를 가집니다. 💾✨

이렇게 해서 조건을 만족하며 문제를 해결할 수 있었습니다. ✅

파이썬 문제풀이 코드


class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        
        cur_value = 1
        result = [1 for _ in range(len(nums))]

        for i in range(len(nums)-1): 
            cur_value *= nums[i]
            result[i+1] *= cur_value
        
        cur_value = 1
        for i in range(len(nums)-1, 0, -1):            
            cur_value *= nums[i]
            result[i-1] *= cur_value
        

        return result

시간복잡도

공간복잡도

Constraints

2 <= nums.length <= 10^5

30 <= nums[i] <= 30

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

Example

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]