[알고리즘/Python] LeetCode 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

Best Time to Buy and Sell Stock - LeetCode

You are given an array prices where prices[i] is the price of a given stock on the ith day.
You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.
Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.
 
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 <= 10^5
0  <= prices[i] <= 10^4

---

💡접근방법1: 현재까지 최저 가격으로 값 갱신하기

 i번째 날에 수익을 최대화하는 방법은 i-1번째 날까지의 주식 가격 중 가장 낮은 가격에 사서 오늘 파는 것이다. 만약 오늘의 가격이 이전까지의 모든 가격보다 낮다면 당연히 주식을 사지 않는 것이 가장 좋은 선택이다. profit이 0인 것이 마이너스인것보다 낫다.

 i번째 날에는 i-1번째 날까지의 최저가격만 알면 되고, 그 이외의 데이터들은 필요가 없다. 따라서 매번 i번째 날까지의 최저가격으로 배열의 원소들을 갱신한다.

 

  1. 기준 날짜 사이에 주식 거래를 통해 얻을 수 있는 최대 가격을 의미하는 변수 max_profit을 0으로 초기화한다.

  2. 두번째 날부터 배열을 돌면서 직전 원소와 비교해서 이익이 발생하는지 확인한다. 이익이 발생한다면, max_profit값과 비교해서 더 큰 이익이 발생할 경우 max_profit값을 갱신해간다.

  3. 각 날짜의 비교가 끝나면 원소를 그 날까지의 최저 가격으로 갱신하기 위해 직전 원소보다 값이 클 경우 (직전 원소는 이전 모든 원소들보다 작거나 같다) 직전 원소의 값으로 대체한다.

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

        return max_profit

 이 방법은 타뷸레이션 접근법을 사용한 Dynamic Programming이기도 하다. f(a,b)를 a번째날부터 b번째 날까지의 주식 최저가격이라고 할때 f(a,b) = min(f(a, b-1) , prices[b])의 점근식을 이용해 구하는 방식이기 때문이다.

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

시간 복잡도: O(N). 전체 배열을 한번 순회하므로 O(N) 복잡도를 가진다.

공간 복잡도: O(1). 기존의 배열을 사용하는 in-place 알고리즘으로 추가 공간이 필요하지 않다.

---

💡 접근방법2:  stack을 사용하여 최저 가격을 기록하기

i번째 날까지의 최저 가격을 기록하기위해 stack 자료구조를 사용하는 방식이다.

 

  1. 기준 날짜 사이에 주식 거래를 통해 얻을 수 있는 최대 가격을 의미하는 변수 max_profit을 0으로 초기화한다. 최저 주식 가격을 기록하는 stack 자료구조로 사용할 빈 배열을 선언한다.

  2.  prices 배열을 돌면서 stack의 top에 있는 원소와 비교하여 현재 가격이 더 크다면 수익을 얻을 수 있다는 의미이다. 이때 얻을 수 있는 수익과 max_profit을 비교하여 더 큰 수익을 얻을 수 있다면 값을 갱신한다. 

  3. 만약 stack의 top에 있는 원소와 비교하여 현재 가격이 더 작다면 stack에 추가한다. stack의 top에는 현재까지의 가장 최저 주식 가격이 기록된다.

from typing import List


class Solution(object):
    def maxProfit(self, prices: List[int]) -> int:
        stack = []
        max_profit = 0
        for p in prices:
            if not stack or stack[-1] > p:
                stack.append(p)
            else:
                profit = p - stack[-1]
                if max_profit < profit:
                    max_profit = profit
        return max_profit

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

시간 복잡도: O(N). 전체 배열을 한번 순회하므로 O(N) 복잡도를 가진다.

공간 복잡도: O(N). prices가 내림차순으로 정렬된 경우 즉, 주식가격이 매일 떨어지는 경우에는 stack에 prices의 모든 원소들이 기록되므로 O(N)만큼의 공간이 필요하다.

---

✅ 정리

◎ 이전 주식 가격을 다 알고 있으면서 현재 시점에서 수익을 최대화할 수 있는 과거 시점을 선택한다는 아이디어는 현실에서는 불가능하다.