[Java] LeetCode 122. Best Time to Buy and Sell Stock II
[Java] LeetCode 122. Best Time to Buy and Sell Stock II
문 제 :
주식의 가격을 담은 일차원 정수배열 prices가 주어진다.
prices[i] 는 그 날 주식의 가격이다.
사용자는 주식을 한 가지만 가지고 있을 수 있다. (이미 주식을 가지고 있다면 판 뒤에 주식을 구매할 수 있다.)
각 날 마다 사용자는 다음 중 하나의 행동을 무조건 해야한다.
1. 주식 사기
2. 주식 팔기
3. 존버 하기
4. 주식 샀다가 그 날 다시 바로 팔기
최대의 이익을 냈을 때, 얼마의 이익을 볼 수 있는지 구해라.
Constraint
{ 1 <= prices.length == 3 * 10^4 }
{ 0 == prices[i]. <= 10^4}
Example )
Input: prices = [7,1,5,3,6,4]
Output: 7
Explanation:
Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Total profit is 4 + 3 = 7.
//////////////////////////////////////////////////////////
Input: prices = [1,2,3,4,5]
Output: 4
Explanation:
Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Total profit is 4.
//////////////////////////////////////////////////////////
Input: prices = [7,6,4,3,1]
Output: 0
Explanation:
There is no way to make a positive profit,
so we never buy the stock to achieve the maximum profit of 0.
접 근 :
Greedy 방식으로 접근했다.
다음과 같은 규칙을 생각하며 코드를 구상했다.
1. 저점에서 구매
2. 고점에서 판매
3. 오르고 있는 중이면 존버
해 결 :
주식을 산 가격 = buy
주식을 파는 가격 = sell
날 마다의 주식 가격을 돌면서 (반복문)
만약 내일 주식 가격이 떨어지게 된다면, -> 오늘이 고점이라는 뜻이다.
따라서 주식을 판다.
팔 때에는 팔 때의 가격에서 내가 산 가격을 뺀 것이 순 이익이다. (profit)
그리고 팔았으니 다음 날 주식을 사야한다. (다다음날 안 오른다해도 바로 팔면 되니깐 손해는 안 본다.)
만약 내일 주식 가격이 오늘보다 더 오른다면, 그리고 내가 팔 가격보다 더 비싸진다면? -> 존버 해야 한다.
그리고 나서 내가 팔 가격을 가장 높은 가격으로 다시 세팅해준다.
그리고 나서 반복문을 종료한 후 ,
아직 거래하지 않은 주식이 있다면 마지막으로 처분해준다.
변수 초기화
int profit=0;
int buy = prices[0];
int sell = prices[0];
결 과 :
class Solution {
public int maxProfit(int[] prices) {
int profit=0;
int buy = prices[0];
int sell = prices[0];
for(int i=0; i<prices.length-1; i++) {
if(prices[i] > prices[i+1]) { // 내일 떨어짐 -> 팔아야함
profit = profit + sell - buy;
buy = prices[i+1]; // 다음 날은 무조건 삼
sell = prices[i+1];
}
else if(prices[i] < prices[i+1] && sell < prices[i+1]) { // 내일 오름 -> 내일 팔려고 존버
sell = prices[i+1];
}
}
profit = profit + sell - buy;
return profit;
}
}