(Leetcode) 238 - Product of Array Except Self
New Year Gift - Curated List of Top 75 LeetCode Questions to Save Your Time
위 링크에 있는 추천 문제들을 시간이 있을때마다 풀어보려고 한다.
https://leetcode.com/problems/product-of-array-except-self/
첫 접근
public int[] productExceptSelf(int[] nums) {
List<Integer> products = new ArrayList<>();
int p = 0;
while (p < nums.length) {
int i = 0;
Integer product = null;
while (i < nums.length) {
if (i == p) {
i++;
continue;
}
if (product == null) {
product = nums[i];
} else {
product *= nums[i];
}
if (product == 0) {
break;
}
i++;
}
products.add(product);
p++;
}
return products.stream().mapToInt(i -> i).toArray();
}
순수하게 다 계산하는 방식이다. 물론 타임아웃이 발생된다.
TC, SC
시간 복잡도는 O(n^2)이고 공간 복잡도는 O(n)이다.
두 번째 접근
public int[] productExceptSelf(int[] nums) {
List<Integer> products = new ArrayList<>();
int result = 1;
int zeroCount = 0;
int p = 0;
while (p < nums.length) {
if (nums[p] != 0) {
result *= nums[p];
} else {
zeroCount++;
}
p++;
}
if (zeroCount >= 2) {
products.addAll(new ArrayList<>(Collections.nCopies(nums.length, 0)));
} else if (zeroCount == 1) {
p = 0;
while (p < nums.length) {
if (nums[p] == 0) {
products.add(result);
} else {
products.add(0);
}
p++;
}
} else {
p = 0;
while (p < nums.length) {
products.add(result / nums[p]);
p++;
}
}
return products.stream().mapToInt(i -> i).toArray();
}
0의 개수에 따른 케이스를 분리하였다.
- 0이 2개 일 때 : 모든 값이 0이다.
- 0이 1개 일 때 : 0인 부분만 값이 있다. 그리고 그 값은 0의 제외한 모든 수의 곱이다.
- 0이 없을 때 : 전체 곱에서 해당 부분(num[i])를 나누어준다.
통과는 하였지만 결과가 아쉬웠다.
TC, SC
시간 복잡도는 O(n)이고 공간 복잡도는 O(n)이다.
더 개선해보기
public int[] productExceptSelf(int[] nums) {
int[] products = new int[nums.length];
int result = 1;
int zeroCount = 0;
int p = 0;
while (p < nums.length) {
if (nums[p] != 0) {
result *= nums[p];
} else {
zeroCount++;
if (zeroCount >= 2) {
Arrays.fill(products, 0);
return products;
}
}
p++;
}
if (zeroCount == 1) {
p = 0;
while (p < nums.length) {
if (nums[p] == 0) {
products[p] = result;
}
p++;
}
} else {
p = 0;
while (p < nums.length) {
products[p] = result / nums[p];
p++;
}
}
return products;
}
예시 input도 간단함에도 7ms가 소요되길래 이건 input이 지저분한게 아니라, 그냥 기본적으로 시간이 많이 걸리는구나 싶어서 개선할 수 있는 부분이 없을지 고민해보았다.
처음에 구현할 때 List 로 해두면 후 가공처리가 편할것 같아서 했는데 오히려 이 부분에서 시간을 소모했나보다 싶어서 Array로 바꾸었더니 바로 2ms로 개선되었다.
TC, SC
시간 복잡도는 O(n)이고 공간 복잡도는 O(n)이다.
prefixProd, suffixProd 로 해결하기 (24.05.29 추가)
누적합(prefixSum) 이라는 알고리즘이 있다.
이를 응용해서 prefixProd와 suffixProd 이란 것을 만든다.
참고로 prefixProd는 앞에서부터 진행하는 누적곱, suffixProd는 뒤에서부터 진행하는 누적곱이다.
예시
예시로 제공된 input 값을 사용해보면 다음과 같을 것이다.
- 입력 : [1, 2, 3, 4]
- prefixProd : [1, 2, 6, 24]
- suffixProd : [24, 24, 12, 4]
- 결과 : [24, 12, 8, 6]
- 결과의 각 값은 나 자신을 제외한 나머지 갑들의 곱이다.
- 결과의 각 값은 prefixProd[i - 1] * suffixProd[i + 1] 이다. 단. 인덱스 범위를 벗어낫을 경우는 1을 곱한다.
- [1 * suffixProd[1], prefixProd[0] * suffixProd[2], prefixProd[1] * suffixProd[3], prefixProd[2] * 1]
코드
public int[] productExceptSelf(int[] nums) {
int[] result = new int[nums.length];
int[] prefixProd = new int[nums.length];
int[] suffixProd = new int[nums.length];
prefixProd[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
prefixProd[i] = prefixProd[i-1] * nums[i];
}
suffixProd[nums.length - 1] = nums[nums.length - 1];
for (int i = nums.length - 2; i > -1; i--) {
suffixProd[i] = suffixProd[i + 1] * nums[i];
}
result[0] = suffixProd[1];
result[nums.length - 1] = prefixProd[nums.length - 2];
for (int i = 1; i < nums.length - 1; i++) {
result[i] = prefixProd[i - 1] * suffixProd[i + 1];
}
return result;
}
TC, SC
시간 복잡도는 O(n)이고 공간 복잡도는 O(n)이다.