Leetcode 714. Best Time to Buy and Sell Stock with Transaction Fee

문제

You are given an array prices where prices[i] is the price of a given stock on the ith day, 
and an integer fee representing a transaction fee.

Find the maximum profit you can achieve. 
You may complete as many transactions as you like, 
but you need to pay the transaction fee for each transaction.

Note:

- You may not engage in multiple transactions simultaneously 
(i.e., you must sell the stock before you buy again).

- The transaction fee is only charged once for each stock purchase and sale.

i번째 날의 주식 가격을 담은 prices 배열이 있습니다.
또한 주식을 판매할때마다 fee 만큼의 비용을 지불해야 합니다.
1주를 매수, 매도 함으로 얻을수 있는 최대의 이익을 구하세요
단 아래 규칙을 따라야 합니다.

• 동일한 날짜에 매수, 매도 주문을 체결할수 없습니다.

예시

Input: prices = [1,3,2,8,4,9], fee = 2
Output: 8
Explanation: 
i = 0 일때 구매 -> i = 3 일때 판매 ( 8 - 1 - 2 원 이익 )
i - 4 일때 구매 -> i = 5 일때 판매 ( 9 - 4 - 2 원 이익 )
2원은 매도 수수료 ( fee )

풀이법

• buy 와 sell 변수를 선언하는데, 이는 가장 최근에 매도, 매수 했을때의 최대 이익을 의미한다.
• 다음 sell 값은 아래와 같은 방식으로 정해진다.
  • 주식을 판매하지 않았다고 가정할시 sell 값이 유지된다.
  • 주식을 판매했다면, 이는 곧 직전에 주식을 구매했다는것이기에 buy 값에 prices[i]를 더하고 fee를 뺀 값이 된다.
  • 판매하지 않았거나 vs 판 했거나 두 선택지중 더 값이 큰것으로 sell값을 정하면 최대 이익을 찾을수 있을것이다.
• buy도 똑같은 방식으로 구할수 있다.
• 단 buy와 sell이 서로서로의 값을 사용하기 때문에, 일단 새로운 buy와 sell을 구해 각각 다른 변수에 임시로 넣고 다시 변수에 넣어야 한다.

class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        buy = -prices[0]
        sell = 0

        for i in range(1, len(prices)):
            buy_changed = max(buy, sell - prices[i])
            sell_changed = max(sell, buy + prices[i] - fee)
            buy = buy_changed
            sell = sell_changed

        return sell

• buy의 초기값이 -prices[0] 인 이유는 이때 주식을 구매했다는것을 가정하기 때문이다.