[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;
    }
}

해결에서 설명한 것과 같이 반복문 안에 조건문을 넣어 작성해준다.