[LeetCode_238] 자신을 제외한 배열의 곱

파이썬으로 배우는 알고리즘 책을 공부하며 풀었던 LeetCode문제들을 재정리해보자.

 

# 문제 설명 

238번 Product of Array Except Self는 주어진 배열에서 output[i]가 자신을 제외한 나머지 모든 요소의 곱셈 결과가 되도록 출력하는 문제이다.

 

단 나눗셈 없이 O(n)에 풀이해야 함.

Example

 

 

# 풀이방법 1 - 왼쪽과 오른쪽 곱셈 후 계산 (내 풀이 - 비효율적) 

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        
        cmltv_f = 1
        cmltv_b = 1
        front = deque()
        back = deque()
        
        len_nums = len(nums)
        
        # 1. 왼쪽/오른쪽 누적 곱 계산후 deque에 저장
        for i in range(len_nums-1):
            cmltv_f *= nums[i]
            cmltv_b *= nums[len_nums - i - 1]
            
            front.append(cmltv_f)
            back.append(cmltv_b)
           
        
        # 2. 왼쪽, 오른쪽 누적 곱 저장값으로 result 배열 계산
        result = []
        
        result.append(back.pop())
        
        for i in range(len_nums-2) : 
            result.append(back.pop() * front.popleft())
            
        result.append(front.popleft())

        return result

아이디어 : for문을 통해 왼쪽과 오른쪽의 누적 값을 계산한 후, 계산한 값을 가지고 최종 result 값을 계산함

- cmltv_f/cmltv_b 변수 : 왼쪽과 오른쪽 누적값 저장 변수

- front/back deque 변수 : 누적 값을 저장하는 큐

- result 리스트 : front와 back 큐에 저장된 값을 가지고 계산된 최종 값 저장 배열 

 

문제 풀고 책의 풀이방법을 봤는데, 저자와 비슷한 방법으로 풀어서 좀 뿌듯했던 문제,,,😁 

아이디어 노트

 

 

# 풀이 방법 2 - 왼쪽 곱셈 결과에 오른쪽 값을 차례대로 곱셈 (책 풀이 참고)

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        
        result = [] # 최종 결과 배열 (1차: 왼쪽 누적 값)
        cmltv = 1 # 누적 값
        
        
        # 1. 왼쪽 누적 합 저장 
        for i in range(0, len(nums)) :
            result.append(cmltv)
            cmltv *= nums[i]
        
        # 2. 왼쪽 누적 결과 값에 오른족 값 차례대로 곱셈
        cmltv = 1
        
        for i in range(len(nums)-1, -1 ,-1):
            result[i] = result[i] * cmltv
            cmltv *= nums[i]
            
        return result

1. 왼쪽 누적 합을 result 배열에 저장 

2. for문으로 왼쪽 누적 결과 값에 오른쪽 값부터 차례대로 곱셈하여 result 배열에 저장

 

| 핵심 |

# 핵심 : append 부터 먼저하면 됨!

for i in range(0, len(nums)) :
            result.append(cmltv)
            cmltv *= nums[i]

 

 

 

# 결과