[리트코드] Product of Array Except Self(python)

리트코드, Product of Array Except Self_자기 자신을 제외한 배열 곱셈

 

TL;DR

• 문제 조건에 따라 배열을 활용하여 문제를 풀 수 있는지

문제 분석

1. 주어진 정수 배열 nums에서 각 원소를 제외한 나머지 원소들의 곱으로 이루어진 배열을 반환한다.
2. 숫자들은 32비트 정수로 한정된다.
3. 시간 복잡도가 O(n)이어야 하며, 나머지 연산을 활용하면 안된다.

 

- 1 : 해결해야 하는 문제 조건에 대해서 말하고 있다.

- 2 : 문제 자체적으로 값의 상-하한을 주고 있다. 파이썬에서는 크게 신경쓰지 않아도 된다.

- 3 : 문제의 제약 조건을 말하고 있다. 이 부분이 굉장히 풀이를 하는데 어렵게 다가왔다.

입출력 형태

입출력 예시

 

- nums : 정수 배열 nums가 주어진다.

- 각 원소를 제외한 곱셈의 결과를 반환한다.

   - 1을 제외한 나머지 원소의 곱은 24이다.

   - 2를 제외한 나머지 원소의 곱은 12이다.

   - 3을 제외한 나머지 원소의 곱은 8이다.

   - 4를 제외한 나머지 원소의 곱은 6이다.

   - [24, 12, 8, 6]을 반환한다.

풀이

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        answer = []
        
        p = 1 # 왼쪽부터 곱하기
        for i in range(len(nums)):
            answer.append(p)
            p *= nums[i]
            
        p = 1 # 오른쪽부터 곱하기
        for i in range(len(nums) - 1, -1, -1):
            answer[i] *= p
            p *= nums[i]
            
        return answer

 

- 시간 복잡도가 O(n)으로 한정되어 있기 때문에 배열의 원소 하나씩 제외하며 나머지를 곱하는 방식을 사용할 수 없다.

- 나눗셈도 사용하면 안된다고 하였기 때문에 배열 전체 원소를 곱한 후, 각 원소를 순회하며 나누는 방법도 사용할 수 없다.

- 문제를 풀기 위해 정한 시간 30분을 초과하였기 때문에 "파이썬 알고리즘 인터뷰" 책의 풀이를 참고하였다.

- 방법은 왼쪽에서부터 곱한 결과와 오른쪽에서부터 곱한 결과를 서로 곱하는 것이다.

 

- 왼쪽에서 곱하기

   - 1로 초기화한 p를 정답 배열에 넣는다.

   - p에 nums의 원소(1)를 곱한다. 그렇게 되면 p = 1이 된다.

   - p를 배열에 넣고, nums의 원소(2)를 곱한다. p = 2

   - p를 배열에 넣고, nums의 원소(3)를 곱한다. p = 6

   - p를 배열에 넣고, nums의 원소(4)를 곱한다. p = 24

   - 이 과정을 거치면 answer에는 [1, 1, 2, 6]이 담기게 된다.

 

- 오른쪽에서 곱하기

    - p를 다시 1로 초기화하고, 이번엔 배열의 뒤에서부터 조회한다.

    - range(시작지점, 끝지점, 단계)로 이루어지기 때문에 코드에서 보는 바와 같이 정리할 수 있다.

    - answer의 마지막 원소에 p를 곱하고, p에 nums의 원소(4)를 곱한다. answer = [1, 1, 2, 6], p = 4

    - 과정을 반복하면 아래와 같이 된다.

        - nums = 3, answer = [1, 1, 8, 6], p = 12

        - nums = 2, answer = [1, 12, 8, 6], p = 24

        - nums = 1, answer = [24, 12, 8, 6], p = 24

  - 정답을 얻을 수 있다.

감상

- 시간 복잡도에 대한 조건과 특정 연산자를 사용하면 안 된다는 조건에 의해 문제의 풀이를 생각해내는 것이 굉장히 어려웠다.

- 생각해낸 방법을 구현하는 것 자체는 range 함수를 원하는 대로 쓸 수 있다면 간단하게 구현할 수 있었다.

- 이런 경우들을 보면, "알고리즘 문제에서 해결하기 위한 방법을 생각하는 것도, 방법을 구현하는 것도 매우 중요하구나"를 다시 확인할 수 있었다. 많이 풀면서 익히는 수 밖에