122. Best Time to Buy and Sell Stock II

 

1. Greedy

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        stack = []
        answer = 0
        for price in prices:
            if not stack:
                stack.append(price)
            else:
                if stack[-1] < price:
                    answer+=price-stack[-1]
                    stack.pop()
                    stack.append(price)
                else:
                    stack.pop()
                    stack.append(price)
        return answer

주어진 날짜에 대한 주식 가격 목록에서 주식을 사고 팔 최댓값을 반환하면 된다.

그리디 하게 생각해서 해결할 수 있는 문제다.

 

[ 1, 3, 7 ]

첫째, 둘째, 셋째 날 주식의 가격이 위와 같다고 가정하면 얻을 수 있는 최대 이익은 6이다.

첫째 날에 사서 셋째 날에 팔아도 되고, 첫째 날에 사서 둘째 날에 팔고, 둘째 날에 사서 셋째 날에 팔아도 된다.

즉 주식을 산 가격보다 비싸면 그냥 팔고, 바로 그날 주식을 사는 것을 반복해도 논리적으로 문제가 없다.

 

[ 5, 2, 6 ]

첫째, 둘째, 셋째 날 주식의 가격이 위와 같다고 가정하면 얻을 수 있는 최대 이익은 4이다.

우선 첫째 날에 주식을 사면 둘째 날에 팔면 손해기 때문에 첫째 날보다 가격이 최초로 높아지는 셋째 날에 팔아야 이득이 난다.

그러므로 첫째 날보다 주식 가격이 저렴한 둘째 날에 주식을 사야 한다.

 

위 2개의 경우를 조합하면 결국 어느 시점에서 주식을 사는지를 정하면 되는데 그 규칙은 다음과 같다.

 

1. 첫째 날 주식을 무조건 산다는 가정하에 시작한다.

2. 현재 날이 사기로 한 주식보다 싸면 살 주식을 현재 날 주식의 가격으로 바꾸고, 같거나 비싸면 사기로 한 주식을 진짜 샀다고 가정하고

(현재 날 주식 가격 - 사기로 한 주식 가격)을 결과에 더해준다. 그 뒤 현재 날 주식을 샀다고 가정한다.

 

이것을 반복하면 된다.