Product of Array Except Self
정수 배열 nums가 주어집니다. 길이가 같은 배열 answer를 반환하세요. 여기서 answer[i]는 인덱스 i에 있는 요소를 제외한 nums의 모든 요소의 곱입니다. 나눗셈을 사용하지 않고 O(n) 시간에 수행하세요.
함수
- numsinteger-array
- 두 개 이상의 요소로 이루어진 정수 배열
- 반환값integer-array
- 인덱스 i의 값이 nums[i]를 제외한 모든 요소의 곱인 배열
제약 조건
2 ≤ nums.length ≤ 104-30 ≤ nums[i] ≤ 30- 0이 아닌
nums의 모든 값의 곱은 32비트 부호 있는 정수에 들어가므로, 계산 과정에서 만들어지는 모든 곱도 들어갑니다.
예제
- 입력
- nums = [2, 3, 4, 5]
- 출력
- [60, 40, 30, 24]
- 설명
- 2를 제외하면 3 × 4 × 5 = 60이 되고, 5를 제외하면 2 × 3 × 4 = 24가 됩니다. 가운데 두 경우도 같은 방식으로 계산합니다. 2 × 4 × 5 = 40이고 2 × 3 × 5 = 30입니다.
- 입력
- nums = [-2, 5, 0, 3]
- 출력
- [0, 0, -30, 0]
- 설명
- 0을 포함하는 모든 곱은 0입니다. 인덱스 2의 곱만 0을 제외하며, -2 × 5 × 3 = -30입니다.
- 입력
- nums = [0, 4, 0, -1]
- 출력
- [0, 0, 0, 0]
- 설명
- 0이 두 개 있으면 모든 곱에 여전히 0이 적어도 하나 포함되므로, 답의 모든 값은 0입니다.
제출 시 숨은 테스트 +14개
후속 질문
반환하는 배열을 제외하고 추가 공간을 O(1)만 사용할 수 있나요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
각 인덱스에 대해 나머지 모든 값을 곱하면 작동하지만, 값이 10,000개라면 약 1억 번의 곱셈이 필요하고 대부분은 반복됩니다. 인덱스
i의 곱은 인덱스i + 1의 곱과 어떤 공통점이 있을까요?nums[i]를 제외한 모든 값은 왼쪽에 있는 값들과 오른쪽에 있는 값들로 나뉩니다. 모든 접두 부분과 모든 접미 부분의 곱을 알고 있다면, 각 답을 구하는 데 곱셈 한 번이면 됩니다.인덱스마다 왼쪽부터 해당 인덱스 앞의 값들의 곱을 답 배열에 채우세요. 시작값은 1입니다. 그런 다음 오른쪽부터 순회하며 인덱스 뒤의 값들의 누적 곱 하나를 유지하세요. 먼저 이를 답에 곱하고, 그다음에
nums[i]를 곱하세요.
풀이
nums[i]를 제외한 모든 값의 곱은 왼쪽 값들의 곱과 오른쪽 값들의 곱을 곱한 것입니다. 전체 곱을 nums[i]로 나누면 더 짧아 보이지만, 여기서는 허용되지 않으며 전체 곱이 0이 되는 경우, 즉 0이 있을 때 문제가 발생합니다. 접두사와 접미사 곱을 사용하면 두 번의 순회로 왼쪽과 오른쪽의 모든 곱을 구할 수 있으므로, 답을 구하는 데 O(n) 시간이 걸립니다. 출력 배열에 왼쪽 곱을 저장하고 변수 하나로 오른쪽 곱을 유지할 수 있으므로, 다른 배열은 필요하지 않습니다.
각 인덱스에 대해 나머지 항목들을 곱하세요
정답이지만 가장 큰 테스트에서는 끝나지 않음
핵심 아이디어
정의를 따르세요. 각 인덱스 i에 대해 곱을 1에서 시작하고, 인덱스 j가 i가 아닌 모든 nums[j]를 곱하세요. 나중에 해당 값을 나누는 대신 그 인덱스를 건너뛰면 0도 문제없이 처리할 수 있습니다. [-2, 5, 0, 3]에서 인덱스 2의 곱은 0을 전혀 보지 않으므로 결과는 -30입니다.
올바른 방법이지만, 같은 작업을 반복합니다. 인덱스 0과 인덱스 1의 곱은 두 값을 제외한 모든 값을 공유하는데도, 어차피 그 값들을 전부 다시 곱합니다. n개의 위치 각각에 n-1번의 곱셈이 필요하며, n = 10^4일 때 총 곱셈 횟수는 약 10^8입니다. C는 1초도 안 되는 시간에 처리하지만, Python, Ruby 또는 R로는 너무 오래 걸립니다.
알고리즘
- 길이가 n인 답 배열을 만듭니다.
- 각 인덱스
i에 대해product를 1로 설정합니다. - 인덱스
j가i가 아닌 모든nums[j]를product에 곱합니다. - 답 배열의 인덱스
i에product를 저장합니다. - 답을 반환합니다.
def productExceptSelf(nums):
n = len(nums)
answer = []
for i in range(n):
product = 1
for j in range(n):
if j != i:
product *= nums[j]
answer.append(product)
return answer접두사 및 접미사 곱 배열
핵심 아이디어
인덱스 i에 있는 곱을 두 부분으로 나눕니다. i 앞의 값들과 뒤의 값들입니다. 이 두 곱을 before[i]와 after[i]라고 부릅니다. 그러면 나눗셈 없이 nums[i]를 제외하고 answer[i] = before[i] × after[i]가 됩니다.
각 배열은 이웃한 값에 한 번 곱해서 만들어집니다. before[0]은 값이 하나도 없을 때의 곱인 1이고, before[i] = before[i-1] × nums[i-1]입니다. 반대쪽 끝에서는 after[n-1]이 1이고 after[i] = after[i+1] × nums[i+1]입니다. [2, 3, 4, 5]의 경우 before = [1, 2, 6, 24]와 after = [60, 20, 5, 1]을 얻으며, 각 위치의 값을 곱하면 [60, 40, 30, 24]가 됩니다.
n단계로 이루어진 세 번의 순회는 O(n) 시간이 걸립니다. 두 보조 배열은 O(n)의 추가 메모리를 사용하며, 다음 접근법에서는 이를 없앱니다.
알고리즘
- 왼쪽부터
before를 채웁니다:before[0] = 1로 설정한 다음, 각 항목을 이전 항목과 이전 값의 곱으로 설정합니다. - 오른쪽부터
after를 채웁니다:after[n-1] = 1로 설정한 다음, 각 항목을 다음 항목과 다음 값의 곱으로 설정합니다. - 모든 인덱스에 대해
answer[i]를before[i] × after[i]로 설정합니다. answer를 반환합니다.
def productExceptSelf(nums):
n = len(nums)
# before[i] = product of nums[0..i-1], after[i] = product of nums[i+1..n-1]
before = [1] * n
after = [1] * n
for i in range(1, n):
before[i] = before[i - 1] * nums[i - 1]
for i in range(n - 2, -1, -1):
after[i] = after[i + 1] * nums[i + 1]
return [before[i] * after[i] for i in range(n)]답변에서 왼쪽 곱은 하나이고, 오른쪽 곱은 하나입니다
핵심 아이디어
전체 after 배열을 한 번에 사용할 필요는 없습니다. 오른쪽 끝에서부터 순회하면 i의 오른쪽에 있는 값들의 곱은 하나의 숫자입니다. 이 값을 right 변수에 저장하고 단계마다 곱셈 한 번으로 갱신하세요.
따라서 첫 번째 순회에서 왼쪽 곱을 정답 배열에 바로 기록하세요. 오른쪽에서 시작하는 두 번째 순회에서는 answer[i]에 right를 곱한 다음에만 right에 nums[i]를 곱하세요. 순서가 중요합니다. 인덱스 i에서 right를 사용할 때는 아직 nums[i]를 포함하면 안 됩니다.
[2, 3, 4, 5]의 경우 첫 번째 순회가 끝나면 [1, 2, 6, 24]가 됩니다. 두 번째 순회에서는 인덱스 3, 2, 1, 0에서 right로 각각 1, 5, 20, 60을 사용하며 배열을 [60, 40, 30, 24]로 만듭니다. 시간 복잡도는 여전히 O(n)이고, 반환하는 배열 외에 추가로 사용하는 메모리는 변수 하나이므로 O(1)입니다.
알고리즘
answer[0] = 1로 설정한 다음, 왼쪽에서 오른쪽으로answer[i] = answer[i-1] × nums[i-1]로 설정합니다.right를 1로 설정합니다.- 마지막 인덱스부터 0까지 역순으로
answer[i]에right를 곱합니다. - 그런 다음
right에nums[i]를 곱합니다. answer를 반환합니다.
def productExceptSelf(nums):
n = len(nums)
# Pass 1: answer[i] = product of everything left of i
answer = [1] * n
for i in range(1, n):
answer[i] = answer[i - 1] * nums[i - 1]
# Pass 2: multiply in the product of everything right of i
right = 1
for i in range(n - 1, -1, -1):
answer[i] *= right
right *= nums[i]
return answer
함정과 경계 사례
여기서 버그는 0, 두 번째 순회에서 두 업데이트를 수행하는 순서, 그리고 배열의 경계에서 발생합니다.
- 전체 곱을
nums[i]로 나누는 방식은 0이 나타나면 실패합니다.[-2, 5, 0, 3]의 전체 곱은 0이며, 인덱스 2에서는 0을 0으로 나누어야 합니다. 0의 개수를 세어 해결할 수도 있지만, 문제에서 나눗셈을 금지합니다. right를 사용하기 전에nums[i]를 곱하면nums[i]가 자기 자신의 곱에 포함됩니다.[2, 3, 4, 5]에서는 마지막 값이 24가 아닌 120이 됩니다.- 왼쪽 곱을 1이 아닌
nums[0]에서 시작하는 경우입니다. 인덱스 0의 왼쪽에는 아무것도 없으므로 왼쪽 곱은 빈 곱인 1이고, 그 결과answer[0]에는 오른쪽 값들만 곱한 결과가 들어갑니다. - 반복문의 범위: 왼쪽 순회에서는
nums[i-1]을 읽으므로 인덱스 1에서 시작합니다. 접미사 배열에서는nums[i+1]을 읽으므로 n-2에서 시작합니다. - 0이 두 개면 모든 답이 0입니다. 0이 하나면 그 0의 인덱스에 있는 값만 제외하고 모든 답이 0입니다. 코드를 신뢰하기 전에 두 경우를 모두 테스트하세요.
자주 묻는 질문4
Product of Array Except Self의 시간 복잡도는 얼마인가요?
접두사 및 접미사 방식은 O(n) 시간에 실행됩니다. 왼쪽에서 한 번, 오른쪽에서 한 번 순회합니다. 왼쪽 곱을 출력 배열에 저장하고 오른쪽 곱을 하나의 누적값으로 유지하므로, 출력 배열 외에 O(1)의 추가 공간만 필요합니다. 각 인덱스마다 나머지 모든 값을 곱하면 O(n²) 시간이 걸립니다.
Product of Array Except Self에서 나눗셈이 허용되지 않는 이유는 무엇인가요?
전체 곱을 nums[i]로 나누면 배열에 0이 있을 때 문제가 발생합니다. 전체 곱이 0이 되고, 0이 있는 인덱스에서는 0으로 나누어야 하기 때문입니다. 이 방식을 작동하게 하려면 0의 개수를 세고 특별한 경우를 처리해야 합니다. 이 규칙은 접두사 곱과 접미사 곱을 사용하도록 유도하며, 이 방식은 특별한 경우를 전혀 처리하지 않아도 0을 다룰 수 있습니다.
출력 배열도 추가 공간으로 계산되나요?
아니요. 어차피 답을 반환해야 하므로, 일반적인 관례에서는 공간 복잡도 계산에서 답을 제외합니다. 따라서 왼쪽 곱들을 여기에 저장하고 오른쪽 곱은 하나의 변수에 유지하면 추가 공간은 O(1)입니다.
Product of Array Except Self는 0을 어떻게 처리하나요?
접두사 및 접미사 곱을 사용하면 0을 위한 특별한 처리가 필요 없습니다. 0을 넘어가는 왼쪽 또는 오른쪽 곱은 0이며, 0 자체의 인덱스에 해당하는 곱에서는 해당 0을 건너뜁니다. 0이 두 개 이상이면 모든 곱에 0이 포함되므로 모든 답은 0입니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
Python
def productExceptSelf(nums):
# 여기에 코드를 작성하세요케이스 1
케이스 2
케이스 3
입력
nums = [2, 3, 4, 5]
기대값
[60, 40, 30, 24]