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

문제

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

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Example 2:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.

Constraints:

• 1 <= prices.length <= 105
• 0 <= prices[i] <= 104

---

✔ 문제접근 #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):
            # index 0 ~ i - 1까지 값들 중 가장 작은 값과 비교한다.
            ans = max(ans, prices[i] - min_val)
            
            # 지금까지 들어온 값들 중 가장 작은 값을 갱신한다.
            min_val = min(min_val, prices[i])
            
        return ans

 

Complexity Analysis

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

• 공간복잡도 : O(1)

---

 

기타풀이 및 회고

배열을 순회하며 지금까지 순회해온 내용들중 최소, 혹은 최대값을 갱신해주는 아이디어가 포인트이다. 마치 다이나믹 프로그래밍에서 시작부터현재위치값까지의 최댓값 혹은 최솟값을 기록해주는 방식과 똑같다. 만약 이런식으로 최대, 최솟값을 갱신해오지 않았다면 완전탐색을 통해서 살 위치와, 팔 위치를 골라야 하기 때문에 시간복잡도 O(N**2)이 나왔을 것이다.