[리트코드] 122. Best Time to Buy and Sell Stock II

문제

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

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.

Constraints:

• 1 <= prices.length <= 3 * 10**4
• 0 <= prices[i] <= 10**4

---

✔ 문제접근 #1 그리디[통과] ⭕

Intuition
가장 낮은 지점일 때 사고, 가장 높은 지점(고점)에서 팔아버린다. 가격이 떨어진다면 그자리에서 사서 그자리에서 팔아버린다. 다음 과정을 반복하며 전체 가격을 순회한다.

Algorithm
전체 가격을 순회하며 바로 직전 가격보다 현재 가격이 더 높다면 계속 상승중이므로 그냥 넘어간다.

만약 이전가격보다 현재가격이 작아진다면 상승세가 멈추었기 때문에 현재가격에서 사버리고 최솟값이 현재가격이므로 다시 팔아버린다. 

 

맨 마지막값일 때 상승중일 수 있기 때문에 팔아준다. 만약 하락중이었다고 하더라도 최솟값은 자신이 될 것이기 때문에 영향을 미치지 않는다.

    def maxProfit(self, prices: List[int]) -> int:
        
        # 값이 오르다가 최대점이 찍힐 때 판다?
        
        n = len(prices)
        min_val = prices[0]
        ans = 0
        for i in range(1, n):
            # 계속 상승중이라면 넘어간다.
            if prices[i - 1] < prices[i]:
                continue
                
            # 상승세가 끊긴다면 i - 1부분이 최대치이다.
            if prices[i - 1] > prices[i]:
                ans += prices[i - 1] - min_val
                min_val = prices[i]
        
        ans += prices[n - 1] - min_val
                
        return ans

 

Complexity Analysis

• 시간 복잡도 : O(N)
  
  • prices 배열을 순차탐색 O(N)

• 공간복잡도 : O(1)
  

---

 

기타풀이 및 회고

이 문제는 파는곳이 1곳이 정답일 수 도있고, 여러곳에서 파는것이 정답일 수 도 있다. 그렇기 때문에 언제 팔아야 최대값을 낼 수 있는지를 생각해 내는 것이 관건다. 그리디 방법이라고 생각할 수 있는데, 바로 계속해서 가격이 상승하다가 최대치를 찍는 순간 파는 것이 가장 이득이라고 생각할 수 있다.