문제 / 예제 / 제한 조건 :
이번 문제도 보자마자는 엄청 쉬워보였는데, 생각보다 어려웠다.
딱 떠올렸을 때, 모든 케이스를 계산하는 방법 외에 다른 방법이 떠오르지 않았다..
통과하는지 보기 위해서 일단 풀어봄
풀이 #1
for문 2개를 써서 모든 경우의 수를 다 계산하고 곱해주는 것.
class Solution {
public int maxProduct(int[] nums) {
int maximumNum = nums[0];
for (int i = 0; i < nums.length; i++) {
int currentMultiple = nums[i];
maximumNum = Math.max(maximumNum, currentMultiple);
for (int j = i + 1; j < nums.length; j++) {
currentMultiple *= nums[j];
maximumNum = Math.max(maximumNum, currentMultiple);
}
}
return maximumNum;
}
}Time Complexity : O(n^2)
Space Complexity : O(1)
이건 너무 꼴찌잖아..(இ﹏இ`｡)
다른 방법을 머릿속으로 계속계속 생각했는데, 전혀~ 모르겠어서
검색 찬쓰
유튜브 3개를 정도 보고, 이해가 안되서 솔루션도 보고 블로그도 보고 했는데 진짜 이해가 안되서...
마지막으로 시도해 본 유튜브로 이해가 쏙쏙 되었다.
https://youtu.be/Y6B-7ZctiW8?si=ohLNflEB_OQa3LCk
유레카~
풀이 #2
일단 나올 수 있는 경우의 수를 생각해보자.
Case1 : all numbers are positive. 모든 수가 양수 일 경우
Case2 : Both positive and negative numbers. 음수와 양수 모두 있는 경우
- Even count of negative numbers. 음수의 개수가 짝수 인 경우
- Odd count of negative numbers. 음수의 개수가 홀수 인 경우
Case3 : Positive, negative and 0. 양수, 음수 그리고 0이 있는 경우
로 생가해 볼 수 있다.
Case1 의 경우와 Case2-1의 경우는 모든 수를 그냥 곱해주면 최대 수가 된다.
Case2 - 2 경우가 복잡하다
최대 수를 만들기 위해서는 일단 음수 1개를 제거하여, 짝수로 만들어줘야만 최대 수를 만들 수 있다.
예시 배열 : 2 3 -2 -5 6 -1 4 인 경우로 보자
| 2 | 3 | -2 | -5 | 6 | -1 | 4 |
만약 -1을 제거한다면
| 2 | 3 | -2 | -5 | 6 | -1 | 4 |
-1의 왼쪽을 모두 곱한 수가 최대 값이 될 것이다.
만약 -2를 제거한다면
| 2 | 3 | -2 | -5 | 6 | -1 | 4 |
-2의 오른쪽을 모두 곱한 수가 최대 값이 될 것 이다.
그래서 결국 왼쪽부터 시작한 곱셈 수와 오른쪽 부터 시작한 곱셈 수 중 큰 수를 저장하고 있으면 된다.!!
한 번 단계별로 생각해보자~
| 2 | 3 | -2 | -5 | 6 | -1 | 4 |
| Left | Right | Maximum |
| nums[0] = 2 | nums[6] = 4 | 4 (2 vs 4) |
| nums[0] * nums[1] = 6 | nums[6] * nums[5] = -4 | 6 (4 vs 6 vs -4) |
| 6 * nums[2] = -12 | -4 * nums[4] = -24 | 6 (6 vs -12 vs -24) |
| -12 * nums[3] = 60 | -24 * nums[3] = 120 | 120 (6 vs 60 vs 120) |
| 60 * nums[4] = 360 | 120 * nums[2] = -240 | 360 |
| 360 * nums[5] = -360 | -240 * nums[1] = -720 | 360 |
| -360 * nums[6] = -1440 | -720 * nums[0] = -1440 | 360 |
그래서 정답은 360!
이제 Case3의 경우,
2 3 0 -5 6 ... 이 있을 때 위의 방식 대로 왼쪽을 계산해 보면,
| Left |
| nums[0] = 2 |
| 2 * nums[1] = 6 |
| 6 * nums[2] = 0 |
| 0 * nums[3] ... |
이런 식으로 계산이 된다.
이렇게 되면 이후의 수들은 다 0이 되기 때문에,
다음 수부터 다시 계산해주기 위해서 0은 1로 변경해서 계산을 해준다.
| Left |
| nums[0] = 2 |
| 2 * nums[1] = 6 |
| 6 * nums[2] = 0 |
이런 방식대로 구현하면~
class Solution {
public int maxProduct(int[] nums) {
int rightIndex = nums.length - 1;
int leftValue = nums[0], rightValue = nums[rightIndex];
int maximumNum = Math.max(leftValue, rightValue);
for (int i = 1; i < nums.length; i++) {
// zero case
rightValue = rightValue == 0 ? 1 : rightValue;
leftValue = leftValue == 0 ? 1 : leftValue;
// left
leftValue *= nums[i];
// right
rightValue *= nums[rightIndex - i];
// maximum
maximumNum = Math.max(maximumNum, Math.max(leftValue, rightValue));
}
return maximumNum;
}
}Time Complexity: O(n)
Space Complexity: O(1)
좋은 결과로 통과하는 것을 볼 수 있다!
빠밤〰️