LeetCode [238]: Product of Array Except Self

📌 LeetCode [238]: Product of Array Except Self

🔗 문제 링크

---

문제 설명 📄

주어진 정수 배열 nums에서, 자신을 제외한 나머지 모든 요소의 곱으로 이루어진 배열을 반환하는 문제입니다.
시간 복잡도는 O(n)이어야 하며, 나눗셈은 사용할 수 없습니다.

---

문제 접근 방식 📋

처음에는 각 인덱스에 대해 나머지 모든 숫자를 곱하는 방식을 생각했지만, 이는 효율적이지 않습니다. 대신, 좌측에서의 누적 곱과 우측에서의 누적 곱을 계산하여 효율적으로 문제를 해결할 수 있습니다.

아이디어 설명 💡

1. 왼쪽 곱(leftResult) 배열:
   • 배열의 각 인덱스에서, 해당 요소의 왼쪽에 있는 숫자들의 곱을 저장합니다.
2. 오른쪽 곱(rightResult) 배열:
   • 배열의 각 인덱스에서, 해당 요소의 오른쪽에 있는 숫자들의 곱을 저장합니다.
3. 최종 결과:
   • answer[i] = leftResult[i - 1] * rightResult[i + 1]
   • 왼쪽 곱과 오른쪽 곱을 곱하여 최종 결과를 계산합니다.

---

Solution 💻

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

        before = 1
        for i in range(length - 1):
            leftResult[i] = before * nums[i]
            before = leftResult[i]

        before = 1
        for i in range(length - 1, 0, -1):
            rightResult[i] = before * nums[i]
            before = rightResult[i]

        answer = []
        for i in range(length):
            answer.append(leftResult[i - 1] * rightResult[(i + 1) % length])

        return answer

시간 복잡도 분석 ⏲️

• 시간 복잡도: O(n)
  • 왼쪽 곱 계산, 오른쪽 곱 계산, 최종 결과 계산의 각 과정이 모두 O(n)입니다.
• 공간 복잡도: O(n)
  • leftResult와 rightResult 배열이 추가로 필요하므로 공간 복잡도는 O(n)입니다.

---

리팩토링 🛠️

개선된 코드 (리스트 없이 해결)

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        length = len(nums)
        answer = [1] * length

        left = 1
        for i in range(length):
            answer[i] = left
            left *= nums[i]

        right = 1
        for i in range(length - 1, -1, -1):
            answer[i] *= right
            right *= nums[i]

        return answer

리팩토링 후 시간 복잡도 분석 ⏲️

• 시간 복잡도: O(n)
  • 두 번의 반복문으로 모든 요소를 순회합니다.
• 공간 복잡도: O(1)
  • 결과 배열 answer 외에 추가 배열을 사용하지 않습니다.

---

코드 설명 📋

1. 왼쪽 곱과 오른쪽 곱을 하나의 배열에 계산합니다.
2. 첫 번째 반복문에서, 왼쪽 곱을 저장합니다.
3. 두 번째 반복문에서, 오른쪽 곱을 결과 배열에 곱합니다.
4. 결과적으로 추가 공간을 사용하지 않고 문제를 해결할 수 있습니다.