[LeetCode] 238. 자신을 제외한 배열의 곱(Product of Array Except Self)
배열을 입력받아 Output [i]가 자신을 제외한 나머지 모든 요소의 곱셈 결과가 되도록 출력하라.
Input: nums = [1,2,3,4]
Output: [24,12,8,6]
*단, 나눗셈을 하지 않고 O(n)에 풀이하라.
사실 좀 어려워서 고민하다가 풀이 제목을 봤다.
보통 저 문제를 풀면 바로 떠오르는 것은
for문을 중복하여 곱해 나간다던지
전체를 곱하고 요소에서 나눠준 값을 넣는다던지가 있는데
전자는 시간 복잡도가 O(n^2)이 돼버리기에 안되고
후자는 문제 주인장이 그렇게 쉽게 풀지 말래서 안된다. ㅋ~
1. 내가 직접 푼 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
left = []
right = []
result = []
p = 1
if len(nums) == 2:
return [1 * nums[1], 1 * nums[0]]
for i in range(len(nums)):
if i == 0 and nums[i] != 0:
left.append(1)
elif i == 0 and nums[i] == 0:
left.append(0)
else:
p *= nums[i - 1]
left.append(p)
p = 1
for i in range(len(nums)):
if i == 0:
right.append(1)
else:
p *= nums[-i]
right.append(p)
right.reverse()
print(right)
for i in range(len(nums)):
result.append(left[i] * right[i])
return result
|
cs |
해설:
for문의 인덱스 i를 기준으로
왼쪽을 먼저 곱하고
그 뒤에 오른쪽을 마저 곱하는 방식이다.
이렇게 말하면 이해가 잘 안될텐데 자세히 설명해보면
주어진 배열이 [1,2,3,4]라 하자.
2를 기준으로 왼쪽을 곱하면 1
3을 기준으로 왼쪽을 곱하면 2
4를 기준으로 왼쪽을 곱하면 6
(1을 기준으로는 곱할게 없으니까 1)
따라서 [1,1,2,6]이 나오게 된다.
여기서 이제 오른쪽 요소를 각각 곱한다.
1을 기준으로 오른쪽을 곱하면 24
2를 기준으로 오른쪽을 곱하면 12
3을 기준으로 오른쪽을 곱하면 4
4를 기준으로 오른쪽을 곱하면 1
[24,12,4,1]이 된다
나온 두 개의 요소마다의 곱으로 계산을 하면
[24,12,8,6]이 된다.
이것을 코드화한 것이 위의 코드이다.
하지만 위의 코드는 보지 말아라.
너무 복잡하고 생각 없이 만들었으니 답지를 보자!
** 깔끔한 답안 **
2. 왼쪽 곱셈 결과에 오른쪽 값을 차례대로 곱셈
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
out = []
p = 1
# 왼쪽 곱셈
for i in range(0,len(nums)):
out.append(p)
p = p * nums[i]
p = 1
# 왼쪽 곱셈 결과에 오른쪽 값을 차례대로 곱셈
for i in range(len(nums) - 1, 0 - 1, -1):
out[i] = out[i] * p
p = p * nums[i]
return out
|
cs |
해설:
위 코드를 깔끔하게 쓴 것에 불과하다.
하지만 나처럼 left, right 두 개로 나누지 않고
하나에 다 곱해버린 것은 더 brilliant! 한 아이디어인 것 같다.
출처 : 파이썬 알고리즘 인터뷰 (글 : 박상길 그림 : 정진호) [책만]