[Java] 122. Best Time to Buy and Sell Stock 2

문제 파악

i날 주식 가격은 prices[i] 과 같이 배열 형태로 주어진다.

 

매일 주식을 살지 팔지 결정해야한다. 

 

결과적으로 얻어지는 최대 수익을 반환해야한다.

 

---

풀이

 

1️⃣ 내림 차순으로 바뀌는 순간 수익 계산

 

풀이가 잘 떠오르지 않아서 몇 가지 예시를 들어봤다.

 

Case 1.
1, 6, 7, 100

위 경우는 1에 사서 6에 팔고 7에 사서 100에 팔면,

1에 사서 100에 파는것보다 손해이다. 6~7 에 공백이 생기기 때문이다.


Case 2.
1, 6, 5, 100

위 경우는 1에 사서 6에 팔고, 5에 사서 100에 팔면,

1에 사서 100에 파는 것보다 이득이다. 5~6 교집합 부분이 생겨 추가적인 이득이 될 수 있다.



Case 3.
1, 6, 6, 100

위 경우는 1에 사서 6에 팔고 6에 사서 100에 판 수익과

1에 사서 100에 판 수익이 같다.

 

결론은, 주식 가격이 오름차순으로 가다가 가격이 떨어지면

 

그 전날 팔고 떨어진 가격으로 다시 사는 방식으로 구현하면 되겠다 생각이 들었다.

 

class Solution {
    public int maxProfit(int[] prices) {
        int profit = 0;
        int buy = prices[0];
        int sell = prices[0];

        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > sell) {
                sell = prices[i];
            } else {
                profit += sell - buy;
                buy = prices[i];
                sell = buy;
            }
        }

        if (buy != sell) {
            profit += sell - buy;
        }


        return profit;
    }
}

 

계속 주식 가격이 오름차순으로 진행되다가 끝난 경우는, 수익을 for문 내에서 계산을 못해주기 때문에 

 

마지막 조건문으로 계산해주어야 한다.

 

결과

 

2️⃣ 다른 풀이

 

다른 풀이를 확인해보니 더 간단하게 해결할 수 있었다.

 

내가 세워놨던 가정 3번을 활용하면, 더 간단하게 풀이할 수 있었다...!

 

Case 3.
1, 6, 6, 100

위 경우는 1에 사서 6에 팔고 6에 사서 100에 판 수익과

1에 사서 100에 판 수익이 같다.

 

오름차순으로 가격이 들어오는 경우 계속 팔면 되는것이다.

 

만약, 내림차순이 되는 순간은 팔지 않고 사기만 하면 된다.

 

class Solution {
    public int maxProfit(int[] prices) {
        int profit = 0;
        int buy = prices[0];
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] >= buy) {
                profit += prices[i] - buy;
                buy = prices[i];
            } else {
                buy = prices[i];
            }
        }
        return profit;
    }
}

 

결과

 

이전 풀이보다 메모리를 조금 더 아낄 수 있었다.

---

 

 

📖 회고

다른 사람의 풀이를 보고 개선한 코드도, 어쩌면 나도 처음에 짤 수 있었을텐데 라는 생각이 들었다.

 

문제를 풀기 위한 상황을 가정하고, 코드로서 구현할 때

 

여러가지 측면을 생각해보고, 코드로서 더 쉽게 구현할 수 있는 부분을 잘 선택해야겠다.