LeetCode는 소프트웨어 엔지니어링 및 코딩 인터뷰 준비를 위한 플랫폼이다. 다양한 프로그래밍 언어로 구현된 코딩 문제가 공하며 알고리즘 능력을 향상시키는데 도움을 준다.

LeetCode에 수 많은 문제 중에 시간을 절약하기 위해 New Year Gift – Curated List of Top 75 LeetCode Questions to Save Your Time 에서 각 카테고리/유형 별로 추천하는 75개 문제를 풀어본다.

이번 글에서는 Array문제인 Product of Array Except Self 문제를 python으로 풀어보았다.

Leetcode 문제설명

이 문제는 입력으로 주어진 정수 배열 nums에서 i에 대한 answer[i]가 배열 내의 다른 모든 요소들의 곱한 값이되는 배열을 반환하는 문제이다. 그리고 이 알고리즘은 O(n) 시간 복잡도를 가지며 나눗셈 연산을 사용하지 않아야 한다. (나누기를 쓰지 말라고 한이유는 모든 값을 곱한후에 다시 나누어주면 되기 때문에)

해당 문제는 https://leetcode.com/problems/product-of-array-except-self/ 에서 확인 할 수 있습니다.

1번 예시를 보면 아래와 같다. 각 배열의 output값은 input[i]을 제외한 수를 곱한다.

input	1	2	3	4
output	2*3*4 = 23	1*3*4 = 12	1*2*4 = 8	1*2*3 = 6

솔루션

1. answer배열을 nums와 동일한 길이를 갖도록 초기화 한다.
2. answer배열을 채우기 위해 nums배열을 왼쪽에서 오른쪽으로 순회하면서 각 요소를 이전 요소의 누적곱으로 업데이트한다.
3. 이번에는 nums배열을 오른쪽에서 왼쪽으로 순회하면서 각 요소를 오른쪽에 있는 모든 요소의 곱과 곱한다.
4. 위 두단계를 거치면 배열에는 각 요소에 대한 곱셈 결과가 저장되어 반환된다.

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        answer = [1] * n  # 결과를 저장할 배열을 1로 초기화

        left, right = 1, 1  # 왼쪽에서 오른쪽으로 누적곱, 오른쪽에서 왼쪽으로 누적곱을 위한 변수 초기화

        # 왼쪽에서 오른쪽으로 누적곱 계산
        for i in range(n):
            answer[i] *= left  # 현재 인덱스까지의 누적곱을 결과 배열에 저장
            left *= nums[i]  # 다음 인덱스의 누적곱 계산

        # 오른쪽에서 왼쪽으로 누적곱 계산 및 결과 계산
        for i in range(n - 1, -1, -1):
            answer[i] *= right  # 현재 인덱스까지의 누적곱을 결과 배열에 저장
            right *= nums[i]  # 다음 인덱스의 누적곱 계산

        return answer  # 최종적으로 찾은 결과 배열 반환

추가 설명

아래 표를 참고하면 보다 직관적으로 이해 할 수 있다.

input	1	2	3	4
left > right		1	1*2	1*2*3
right > left	2*3*4	3*4	4
output	23	12	8	6

다음 문제는 Maximum Subarray 입니다.

LeetCode 코딩테스트 Maximum Subarray – Array (5)