LeetCode 238. Product of Array Except Self

자기 자신을 제외한 나머지 수들의 곱을 배열로 출력하는 문제이다.

[1, 2, 3, 4]가 주어진다면 정답은 [(1을 제외한 2, 3, 4의 곱인 24), (2를 제외한 1, 3, 4의 곱인 12), ...] = [24, 12, 8, 6]이다.

풀이

나의 풀이 (오답)

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        answer = []
        for i in nums:
            list = nums.copy()
            list.remove(i)
            mul = prod(list)	// from math import prod : 배열 원소들의 곱
            answer.append(int(mul))
        return answer

원본 배열을 복사하고 반복문을 통해 원소를 하나씩 빼고 곱을 한 뒤 정답 배열에 추가하는 방법을 생각해서 구현했다.

테스트 케이스는 성공하였지만, 제출하고 나니 time limit으로 성공하지 못하였다.

굉장히 긴 배열이었는데, 그 배열을 복사하는데서 많은 시간이 소모되는 것 같았다.

결과값1

---

정답 풀이

def productExceptSelf2(self, nums: List[int]) -> List[int]:
    answer = []
    p = 1
    for i in nums:
        answer.append(p)
        p = p * i
    p = 1
    for i in range(len(nums) - 1, -1, -1):
        answer[i] = answer[i] * p
        p = p * nums[i]
    return answer

위 풀이에서는 반복문이 두 번 등장하는데

 

첫 번째 반복문에서는 자기 자신의 왼쪽 원소들을 곱한 뒤 정답 배열에 추가한다.

[1, 2, 3, 4]에서 첫 번째 원소는 왼쪽 원소가 없으므로 1로 고정, 그다음부터는 다음 원소를 곱해서 추가한다.

위 조건을 만족하기 위해 p라는 변수를 사용하였다.

최초의 p를 1로 지정해서 첫 번째 순서로 삽입한 뒤 배열의 첫 원소인 1을 곱해서 두 번째로 삽입, 1이 곱하여진 p에 다음 원소인 2를 곱해서 세 번째로 삽입, 1과 2가 곱해진 p에 다음 원소인 3을 곱해서 네 번째로 삽입하였다.

[1(p), 1(p)*1, 1*1(p)*2, 1*1*2(p)*3] = [1, 1, 2, 6]

* 만약 곱셈이 아닌 덧셈이었다면 p가 1이 아닌 0이 되었겠지...

 

두 번째 반복문에서는 정답 배열에서 자기 자신의 오른쪽 원소들을 곱하였다.

만약 왼쪽 곱 배열, 오른쪽 곱 배열을 두 개 만든다면 O(n)이 되지만, answer 배열을 재사용하면 O(1)이 되어 공간복잡도가 줄어든다.

range(x, y, z)로 인자가 3개인 반복문을 사용하였는데,

x = 시작점 = len(nums) - 1 = 배열의 마지막 인덱스, y = 끝점 = -1 = 인덱스 0까지, z = step size = -1 = 하나씩 감소 이다.

마찬가지로 p를 1로 지정해서 마지막 원소 오른쪽은 아무것도 없으니까 1을 곱한 뒤 다음 원소를 하나씩 곱한 값을 p로 사용한 뒤 배열에 삽입하였다.

[1, 1, 2, 6]에서 끝에서부터 1(p)*6 → 1*4(p)*2 → 1*4*3(p)*1 → 1*4*3*2(p)*1 순서가 된다. [24, 12, 8, 6]

 

 

결과값