https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/
코드설명
탐욕법(Greedy) 을 활용합니다.
문제의 규칙에 보면, 하루에 매수와 매도를 동시에 할 수 잇습니다 라는 규칙이 존재합니다.
이를 통하여, 가격이 상승할경우 바로 사고 판다면 최대의 이득을 낼 수 있음을 알 수 있습니다.
예로들어, 만약 2번쨰 날에 주식가격이 2000만원이고, 3번쨰 날에 5000만원이면, 반드시 2번쨰 날에 구매했다가, 3번쨰 날에 판매하는 것이 이득입니다.
처음에 제가 헷갈렸던 부분은
만약 [1, 2, 1억, 1억 1원] 이라고 가정해봅시다.
만약 위의 하루에 매수와 매도를 동시에 할 수 없다라는 조건을 온전히 이해하지 못했다면, 위의 경우에서 2 -1 + 1억 1원 - 1억 으로 총 2원의 이득밖에 못내니깐 이 코드가 틀린것 아닌가하는 생각이 듭니다.
하지만, ( 2 - 1) + (1억 - 2) + (1억 1원 - 1억) 으로 하루에 매수매도를 동시에 한다는 조건을 통하여 이전날보다 더 높은 가격의 주식으로 이득을 볼 수 있다면, 바로 파는 것이 항상 이득임을 알 수 있습니다.
코드
정답코드1입니다.
class Solution {
public int maxProfit(int[] prices) {
int answer = 0;
for(int i=1; i<prices.length; i++){
if(prices[i] > prices[i-1]){
answer += prices[i] - prices[i-1];
}
}
return answer;
}
}
처음에 작성한 틀린 코드입니다.
class Solution {
public int maxProfit(int[] prices) {
int buyPrice = prices[0];
int sellPrice = prices[0];
int answer = 0;
for(int i=1; i<prices.length; i++){
if(buyPrice < prices[i]){
sellPrice = Math.max(sellPrice, prices[i]);
answer += sellPrice - buyPrice;
}else if(buyPrice >= prices[i]){
buyPrice = prices[i];
}
}
if(buyPrice < sellPrice) answer += sellPrice - buyPrice;
return answer;
}
}