[알고리즘/Python] LeetCode 122. Best Time to Buy and Sell Stock 2

문제

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/?envType=study-plan-v2&envId=top-interview-150

Best Time to Buy and Sell Stock II - LeetCode

 

You are given an integer array prices where prices[i] is the price of a given stock on the ith day.
On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.
Find and return the maximum profit you can achieve.
 
Example 1:
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.

Example 2:
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.
 
Example 3:
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.

---

 이전에 풀어본 LeetCode 121. Best Time to Buy and Sell Stock 문제에서는 한번만 사고 팔 수 있었던 반면에 현재 문제에서는 이익을 최대화하기 위해 몇번이고 사고 팔 수 있다는 점이다. Example 1의 경우 121 문제의 경우에는 한번만 사고 팔 수 있기 때문에 day 2에 사서 day 5에 파는 것이 이익을 5로 최대화하는 방법이다. 하지만 현재 문제에서는 두번 사고 두번 팔아 더 큰 이익(이익 7)을 얻을 수 있다. 

접근 방식: Dynamic Programming

DP[i]을 0번날부터 i번째날까 얻을 수 있는 최대 이익이라고 할때, DP[i] = DP[i-1] + (prices[i] - prices[i-1] 단, prices[i-1] < prices[i])로 구할 수 있다.

 

  1. i번째 날까지 얻을 수 있는 최대 이익을 기록하기 위해 길이가 prices와 같은 배열 dp를 초기화한다. 

  2. 두번째 날부터 prices배열을 순회하면서 오늘까지 얻을 수 있는 최대 이익을 구한다. 오늘까지 얻을 수 있는 최대 이익은 어제까지 얻을 수 있었던 최대 이익에 어제 사서 오늘 팔 경우 얻을 수 있는 이익을 더한 것을 의미한다. 단, 어제 가격이 오늘보다 높은 경우 주식을 사지 않아야한다.

  3. dp[-1]의 원소를 반환한다. dp[-1]에는 0번째 날부터 i번째 날까지 얻을 수 있는 최대 이익을 의미한다.

 

class Solution(object):
    def maxProfit(self, prices: List[int]):
        dp = [0] * len(prices)
        for i in range(1, len(prices)):
            dp[i] = dp[i - 1]
            if prices[i] > prices[i - 1]:
                dp[i] += prices[i] - prices[i - 1]

        return dp[-1]

✔️시간 복잡도 및 공간 복잡도

시간 복잡도: O(N). prices 배열을 한번 순회한다.

공간 복잡도: O(N). prices 배열 길이만큼의 새로운 dp 배열이 필요하다.

---

🤔 다른 사람의 풀이: 그리디 알고리즘

 profit을 극대화하는 방법은 매번 이익을 얻을 수 있다면 샀다가 파는 것이다. 따라서, 이 풀이는 매일 얻을 수 있는 이익을 누적시켜 가는 방식이다.

class Solution(object):
    def maxProfit(self, prices: List[int]):
        profit = 0
        for i in range(1, len(prices)):
            if prices[i-1] < prices[i]:
                profit += (prices[i] - prices[i-1])
        return profit

 이 방법은 현재 값이 이전 값보다 오른 경우에 항상 이익을 취하는 방식으로, 오늘 이익을 얻을 수 있는 선택을 하면 전체 이익이 최대화되는 그리디 알고리즘으로 볼 수 있다. 

 배열을 한번 순회하기 때문에 O(N) 시간복잡도를 가지고 새로운 배열 없이 profit 변수만 새로 선언하므로 O(1) 공간복잡도를 가진다.

---

✅ 정리

◎ 내일 주식 가격이 오를 거라는 것을 알 수 있다면 얼마나 좋을까.