11. Product of Array Except Self

🎯 leetcode - 238. Product of Array Except Self

---

🤔 나의 풀이

📌 문제

- 파이썬 알고리즘 인터뷰 11번 문제
- 자신을 제외한 배열의 곱 구하기

📌 날짜

2020.01.22

📌 시도 횟수

3 try

💡 Code

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        result = []
        mul = 1
        zero_count = 0
        for num in nums:
            if num == 0:
                zero_count += 1
            else:
                mul *= num
        if zero_count > 1:
            return [0 for i in range(len(nums))]

        for num in nums:
            if num == 0:
                result.append(mul)
            elif num != 0 and zero_count == 1:
                result.append(0)
            else:
                result.append(int(mul / num))
        return result

💡 문제 해결 방법

- 미리 전체 값을 구해놓고 각 항목별로 자신을 나누어 푼다. 
- 이 때 고려해야 할 조건이 바로 0의 유무이다.
1. 0이 2개 이상이면 무조건 결과값은 [0, 0, 0...]이다.
2-1. 0이 1개인 경우에는 0을 제외한 나머지 값들의 곱을 구해놓는다.
2-2. 만약 숫자가 0이면 나머지 값들의 곱을 출력한다.
2-3. 숫자가 0이 아니면 곱은 0이므로 0을 출력한다.
3. 0이 없으면 일반적으로 풀면 된다.

💡 새롭게 알게 된 점

- 헉ㅠㅠ 다 풀고 알게 된 점인데 이 문제는 나눗셈을 하지 않고 푸는 문제였다!🤯

❌ (한번에 맞추지 못한 경우) 오답의 원인

- 처음 시도한 코드는 타임 아웃이 발생했다.
> 현재 숫자를 기준으로 왼쪽, 오른쪽 부분을 나누어 곱을 계산하도록 했다.
> 이 과정에서 2중 for문을 사용하여 타임 아웃이 생겼다.

- 2번째, 3번째 코드는 0의 개수와 조건을 제대로 고려하지 못해 오류가 발생했다.

---

😉 다른 풀이

📌 하나. 왼쪽, 오른쪽 따로 구하고 합치기

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        result = []
        left = 1
        right = 1

        for num in nums:
            result.append(left)
            left = left * num

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

        return result

💡 풀이 추가 설명 - 그림을 보고 이해해요

💡 새롭게 알게 된 점

- 풀이가 신기하고 재미있다ㅎㅎ

---