문제 / 예시 / 제한조건
처음에 보고는 간단하게 생각했음.
122번 문제 푼 것에서 transcation 이 발생 할 때마다, 배열에 저장하고
가장 큰 수 2개를 뽑아서 더하면 되는 문제라고 생각함
예를 들어,
1 1 2 4 2 5 7 2 4 9 0
이렇게 있으면
buy 1 -> sell 4 : profit = 3
buy 2 -> sell 7 : profit = 5
buy 2 -> sell 9 : profit = 7
가 되고
가장 큰 두 수 7,5 를 더해서 12가 된다고 생각함.
class Solution {
public int maxProfit(int[] prices) {
if(prices.length <= 1) {
return 0;
}
int[] savedProfit = new int[prices.length];
int savingIndex = 0;
int buyTime = 0, sellTime = 1;
while (sellTime < prices.length) {
if (prices[sellTime] < prices[buyTime]) {
buyTime = sellTime;
sellTime++;
} else {
if (sellTime < prices.length - 1 && prices[sellTime] > prices[sellTime + 1]) {
savedProfit[savingIndex] = prices[sellTime] - prices[buyTime];
savingIndex++;
buyTime = sellTime;
sellTime = buyTime + 1;
} else if (sellTime >= prices.length - 1) {
savedProfit[savingIndex] = prices[sellTime] - prices[buyTime];
savingIndex++;
sellTime++;
} else {
sellTime++;
}
}
}
Arrays.sort(savedProfit);
return savedProfit[savedProfit.length-1] + savedProfit[savedProfit.length-2];
}
}
근데 아니였다!! 두둔
1 1 2 4 2 5 7 2 4 9 0
이렇게 있으면
buy 1 -> sell 7 : profit = 6
buy 2 -> sell 9 : profit = 7
이렇게 가장 큰 두개의 transaction 이 발생한다.
어떻게 해야 할 지 감이 전혀 안잡혀서, 영상을 엄청 많이 봤다.
https://youtu.be/37s1_xBiqH0?si=zjHPF9FP0kQgI8Dz
https://youtu.be/gVavspgEHyM?si=XltrueYAezhrDQoI
https://youtu.be/q4Vr307dOzs?si=rMqYwb5o6aO9UnEe
나오면 있는 영상을 다 봤는데 위에 두개가 가장 도움이 되었다.
특히 첫 번째 영상은 이해가 안되서 한 5번은 본 듯
그러다가 갑자기 이해가 되서(?) 문제를 풀었다.
일단 발생 할 수 있는 Transcation 은
Buy -> Sell -> Buy -> Sell 이다.
그래서 2개의 Transcation으로 나누어 생각을 해보는 것이다.
1번째 Transcation은 왼쪽부터 Buy point 를 찾는 것으로 시작해서 가장 큰 profit을 찾으면 된다.
Buy point는 어떻게 찾는가?
가장 저점에 사서 고점에 파는 것이 가장 큰 이익을 남길 수 있다.
고로, 가장 저점(minimum) 이 올바른 Buy point로 지정하면 된다.
2번째 Transcation은 오른쪽 끝 지점에서 부터 Sell point를 찾는 것으로 시작해서 가장 큰 profit을 찾으면 된다.
그렇다면 Sell point를 어떻게 찾으면 좋을까?
가장 저점에 사서 고점에 파는 것이 가장 큰 이익이니까
가장 고점(maximum)이 올바른 Sell point가 되겠다.
이렇게하면
1 st Transcation :
| 1 | 1 | 2 | 4 | 2 | 5 | 7 | 2 | 4 | 9 | 0 | |
| min | 1 | 1 | 1 | 1 | 1 | ||||||
| profit | 0 | 0 | 1 | 3 |
여기서 2의 경우에 profit값은 2-1 = 1 이지만, 가장 큰 profit값을 유지해서 적어준다. 고로 3!
| 1 | 1 | 2 | 4 | 2 | 5 | 7 | 2 | 4 | 9 | 0 | |
| min | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| profit | 0 | 0 | 1 | 3 | 3 | 4 | 6 | 6 | 6 | 8 | 8 |
이렇게 할 수 있다.
그리고 2nd Transaction은 오른쪽부터 해주면 된다.
| 1 | 1 | 2 | 4 | 2 | 5 | 7 | 2 | 4 | 9 | 0 | |
| max | 9 | 0 | |||||||||
| profit | 0 | 0 |
이렇게 차근차근 채워주면
| 1 | 1 | 2 | 4 | 2 | 5 | 7 | 2 | 4 | 9 | 0 | |
| max | 9 | 9 | 9 | 9 | 9 | 9 | 9 | 9 | 9 | 9 | 0 |
| profit | 8 | 8 | 7 | 7 | 7 | 7 | 7 | 7 | 5 | 0 | 0 |
이렇게 완성된다!
그렇게 두 표에서 동시에 가장 큰 값을 갖고 있는 포인트를 찾아주면 그 포인트가 바로 두 거래를 나누는 포인트가 되는 것!
| 1 | 1 | 2 | 4 | 2 | 5 | 7 | 2 | 4 | 9 | 0 | |
| profit | 0 | 0 | 1 | 3 | 3 | 4 | 6 | 6 | 6 | 8 | 8 |
| 1 | 1 | 2 | 4 | 2 | 5 | 7 | 2 | 4 | 9 | 0 | |
| profit | 8 | 8 | 7 | 7 | 7 | 7 | 7 | 7 | 5 | 0 | 0 |
고롷게 하면 된다!
내 정답 코드
class Solution {
public int maxProfit(int[] prices) {
int maxProfit = 0;
// 1. 1st transaction from left to right - find min.
int[] left = new int[prices.length];
int min = prices[0];
left[0] = 0; // for memorization to remember maximum profit of 1st transaction.
for(int i=1; i<prices.length; i++) {
min = Math.min(min, prices[i]);
left[i] = Math.max(left[i-1], prices[i] - min );
}
// 2. 2nd transaction from right to left - find max.
int[] right = new int[prices.length];
int max = prices[prices.length-1];
right[prices.length-1] = 0; // for memorization to remember maximum profit of 2nd transaction.
for(int i=prices.length-2; i>=0; i--) {
max = Math.max(max, prices[i]);
right[i] = Math.max(right[i+1], max - prices[i]);
}
// 3. find maxProfit
for(int i=0; i<prices.length; i++) {
maxProfit = Math.max(maxProfit, left[i] + right[i]);
}
return maxProfit;
}
}
Time Complexity : O(n)
Space Complexity : O(n)
진짜 이거 이해하느라 3일동안 붙잡고 있었는데!!!
드디어!!!!