배열을 입력받아 output[i]가 자신을 제외한 나머지 모든 요소의 곱셈 결과가 되도록 출력하라.
- 주의 : 나눗셈을 하지 않고 O(n)에 풀이하라.
이 문제를 보고 맨처음 든 생각은 전체곱에서 나누는 것이다. 그런데 나눗셈을 하면 안된다고 적혀있으니 다음 방법은 본인을 제외한 모든 수를 곱하는 것인데 이 또한 n 제곱의 시간이 걸리므로 불가능 하다.
보통 이러할 때 쓸 수 있는 방법은 시간 대신 메모리를 쓰는 것이다. 본인의 왼쪽까지의 순차적으로 누적 곱을 저장한 배열과 본인의 오른쪽 까지의 순차적으로 누적 곱을 저장한 값을 활용하여 문제를 풀이한다.
예를들어, [1,2,3,4] 라는 배열이 있다고 가정하자.
먼저 자신의 왼쪽 까지의 순차적 곱을 정리한 배열은 [1, 1, 2, 6]이 될 것이다. 그리고 자신의 오른쪽 까지의 순차적 곱을 정리한 배열은 [24, 12, 4, 1] 이 될 것이다. 이 두 배열을 곱하면 각 자리(i)에서 자신을 제외한 나머지 모든 요소의 곱셈의 결과인 [24, 12, 8, 6]이 될 것이다.
이를 구현해보자. 먼저 결과를 저장할 out 배열에 1을 추가해주고, 오른쪽 순차 곱을 저장할 p 변수를 1로 초기화해준다.
out = []
p = 1
out.append(1)
그 다음 본인의 왼쪽까지의 곱셈결과를 out 배열에 저장한다.
for i in range(len(nums)-1):
out.append(out[-1] * nums[i])
그 다음 본인의 오른쪽까지의 곱셈결과를 변수 p에 저장하고, 그 결과를 활용하여 out 결과를 도출한다.
for i in range(len(nums)-1, -1, -1):
out[i] *= p
p *= nums[i]
전체 코드는 다음과 같다.
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
out = []
p = 1
out.append(1)
for i in range(len(nums)-1):
out.append(out[-1] * nums[i])
for i in range(len(nums)-1, -1, -1):
out[i] *= p
p *= nums[i]
return out
'코딩테스트 > 알고리즘' 카테고리의 다른 글
[Q. 13] 팰린드롬 연결 리스트 (0) | 2023.03.21 |
---|---|
[Q. 12] 주식을 사고팔기 가장 좋은 시점 (0) | 2023.03.21 |
[Q. 10] 배열 파티션 1 (0) | 2023.03.20 |
[Q. 09] 세 수의 합 (0) | 2023.03.20 |
[Q. 08] 빗물 트래핑 (0) | 2023.03.20 |