문제 / 예제 / 제한 조건 :
처음에 문제 보자마자 엄청 쉬워보였다.
# 풀이 1
내가 생각했던 방식은 [1,2,3,4] 가 있다면
이 값을 모두 곱해둔 값을 하나 가지고 있고 -> 24
result를 저장 할 때, nums[i]로 나누어서 저장하면 된다고 생각했다.
class Solution {
public int[] productExceptSelf(int[] nums) {
int[] results = new int[nums.length];
int allMultipleValue = 1;
for (int num : nums) {
allMultipleValue *= num;
}
for (int i = 0; i < nums.length; i++) {
results[i] = nums[i] == 0 ? 0 : (allMultipleValue / nums[i]);
}
return results;
}
}Time complexity : O(n)
Space complexity : O(n)
그래서 이렇게 나왔는데, 0이 중간에 있는 두 번째 예시의 경우 적합하지 않은 방식이였다.
그래서 생각해낸 두번째 방법
# 풀이 2
전체적인 플로우는 1번 풀이법과 같으나
nums의 멤버로 0이 1개만 포함되어 있는 경우 / 2개 이상 포함되어 있는 경우 / 없는 경우 로 나누어서 생각했다.
왜냐하면
1. 0이 1개 포함되어 있는 경우, 0의 인덱스를 제외한 나머지 인덱스 들의 결과 값은 0이 된다.
2. 0이 2개 이상 포함되어 있는 경우, 결과 값은 모두 0
3. 0이 1개도 포함되어 있지 않은 경우, 풀이 1의 방법을 그대로 사용하면 된다.
그래서 나는 위의 경우를 zeroIndex의 값을 달리해주는 것으로 구분하였다.
1. 0이 1개 포함되어 있는 경우, zeroIndex = 0이 위치한 index
2. 0이 2개 이상 포함되어 있는 경우, zeroIndex = -99
3. 0이 1개도 포함되어 있지 않은 경우, zeroIndex = -1
class Solution {
public int[] productExceptSelf(int[] nums) {
int zeroIndex = -1; // 0's count == 1 -> index / 0's count > 1 -> -99 / 0's count == 0 -> -1
int allMultipleValue = 1;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == 0) {
zeroIndex = zeroIndex == -1 ? i : -99;
} else {
allMultipleValue *= nums[i];
}
}
for (int i = 0; i < nums.length; i++) {
if(zeroIndex == -99) {
nums[i] = 0;
} else if(zeroIndex == -1){
nums[i] = allMultipleValue / nums[i];
} else {
if(zeroIndex == i) {
nums[i] = allMultipleValue;
} else {
nums[i] = 0;
}
}
}
return nums;
}
}Time complexity : O(n)
Space complexity : O(1)
통과를 하긴 했으나 문제 풀이가 깔끔한 것 같지 않아서 유튜브를 검색
유튜브에서 풀이 접근 하는 방법까지만 보았다.
https://www.youtube.com/watch?v=bNvIQI2wAjk
완전 유레카!!
인덱스 앞 뒤를 따로 계산해주고 그것을 곱해주면 된다니 !!!!
풀이 3
| nums | 1 | 2 | 3 | 4 |
가 있는 경우
| prefix | ||||
| suffix |
이렇게 두 개의 배열을 만들어서 각 인덱스 전(prefix) 후(suffix) 의 값을 곱한 결과를 넣는다.
예를 들어
prefix의 경우
| prefix | 1 |
시작 부분은 nums[0] 전에 곱할 숫자가 없어서 1
| prefix | 1 | 1 |
nums[1] 전의 수 : nums[0] 이므로 nums[0]
| prefix | 1 | 1 | 2 |
nums[2] 전의 수 : nums[0] * nums[1] = 2
| prefix | 1 | 1 | 2 | 6 |
nums[3] 전의 수 : nums[0] * nums[1] * nums[2] = 6
이 것을 다르게 표현하면 prefix[2] * nums[2] 가 된다.
따라서 prefix[i] = prefix[i-1] * nums[i-1]이 된다!
suffix 의 경우, 뒤부터 시작
| suffix | 1 |
시작 부분은 nums[3] 뒤에 곱할 숫자가 없어서 1
| suffix | 4 | 1 |
nums[2] 뒤의 수 : nums[3] 이므로 nums[3]
| suffix | 12 | 4 | 1 |
nums[1] 뒤의 수 : nums[3] * nums[2] = 12
| suffix | 24 | 12 | 4 | 1 |
nums[0] 뒤의 수 : nums[3] * nums[2] * nums[1] = 24
이 것을 다르게 표현하면 suffix[1] * nums[0] 가 된다.
따라서 suffix[i] = suffix[i+1] * nums[i+1]이 된다!
그리고 이제 결과 값은, 각각의 값을 곱하면 된다.
| prefix | 1 | 1 | 2 | 6 |
| suffix | 24 | 12 | 4 | 1 |
| result | 24 | 12 | 8 | 6 |
class Solution {
public int[] productExceptSelf(int[] nums) {
int[] prefix = new int[nums.length];
int[] suffix = new int[nums.length];
int[] result = new int[nums.length];
// prefix
prefix[0] = 1;
for(int i=1; i<nums.length; i++) {
prefix[i] = prefix[i-1] * nums[i-1];
}
// suffix
suffix[nums.length-1] = 1;
for(int i=nums.length-2; i>=0; i--) {
suffix[i] = suffix[i+1] * nums[i+1];
}
for(int i=0; i<nums.length; i++) {
result[i] = prefix[i] * suffix[i];
}
return result;
}
}Time complexity : O(n)
Space complexity : O(n)
이 방식보다 빠를 수 있을까 ? 생각하다가
한 번에 해보자 ! 생각했다
풀이 4
class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] result = new int[nums.length];
// prefix
result[0] = 1;
for(int i=1; i<n; i++) {
result[i] = result[i-1] * nums[i-1];
}
// suffix & result
int suffixMultiple = 1;
for(int i=n - 1; i>=0; i--) {
result[i] *= suffixMultiple;
suffixMultiple *= nums[i];
}
return result;
}
}Time complexity : O(n)
Space complexity : O(n)
신기하다 유레카 !~!