💡 Product of Array Except Self
◽ 문제
-
자신을 제외한 모든 수의 곱을 구해야 하는 문제이다.
-
문제 제약 상 나눗셈을 사용할 수 없게되어 있다.
-
복잡도 O(n)에 풀어야한다.
◽ 문제 해결 전략
-
처음 문제를 보자마자 바로 생각난 것은 for문을 돌리면서 자신이 아닌 수를 체크해 자신을 제외한 모든 수를 곱한 것을 새로운 배열에 넣는 것이었지만 이를 위해서는 필수적으로 이중 for문을 사용하게 되고 이중 for문의 시간복잡도인 O(N^2)가 문제의 조건인 시간 복잡도 O(n)을 만족할 수 없게 된다.
-
문제의 조건인 시간복잡도 O(n)을 만족하기위해서 일단 이중 for문은 사용하면 안된다는 결론이나왔다.
- 오른쪽 지점은 왼쪽에서 시작해서 자신의 위치 직전까지 곱하면 되고 왼쪽 지점은 오른쪽에서 시작해서 자신의 위치 직전까지 곱하면 된다.
즉 이중 for문을 사용하지않으면서 자기 자신을 제외하고 왼쪽의 모든 곱과 오른쪽의 모든 곱을 구해 그 둘을 곱하면된다.
◽ 풀이
# class Solution:
# def productExceptSelf(self, nums: List[int]) -> List[int]:
# output = []
#
# temp = 1 #곱할 값 곱셈이니깐 1부터 시작
# # 자기 자신을 제외하고 왼쪽에 있는 값 곱셈
# for i in range(len(nums)): #nums의 수 만큼 반복
# output.append(temp) #temp를 붙힌다 > 왼쪽으로 이동시킴
# temp *= nums[i] #왼쪽부터 차례대로 곱셈한다.
#
# temp = 1 #초기화
# # 자기 자신을 제외하고 오른쪽에 있는 값 곱셈
# for i in range(len(nums) - 1, -1, -1):
# 맨 마지막으로부터 시작해서, 맨마지막값까지(첫번째),-1씩 감소 = nums를 역순으로 탐색
# output[i] *= temp #곱셈
# temp *= nums[i] #오른쪽부터 차례대로 곱셈한다.
#
# return output💡 배운 점
◽ append( )
array.append(x)
-
append는 덧붙인다는 뜻으로 괄호( ) 안에 값을 입력하면 새로운 요소를 array 맨 끝에 객체로 추가한다.
-
리스트 마지막에 요소를 추가하는 방법이다.
문제 풀이에서 8번째 줄을보면 append()함수를 p를 초기화 하기전에 넣어주었는데 이는 p의 초기값이 1이기 때문에 첫 번째 값 곱셈은 항상 1이며 마지막 값 곱셈을 항상 제외하여 주는 것이다.
-
원래의 크기에 초깃값 1 뒤에 append로 붙이는 것 이기에 마지막 값을 제외된다.
-
8번째줄은 자신을 제외한 왼쪽에있는 값을 곱하기위한 코드이다.
