[DP]99클럽 코테 스터디 40일차 TIL + 0121-best-time-to-buy-and-sell-stock

121. Best Time to Buy and Sell Stock

Easy

---

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 <= 105
• 0 <= prices[i] <= 104

 

<내 코드>

 

- 첫번째 시도

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

        min_v = prices[0]
        max_v = None

        min_index = 0
        for index ,price in enumerate(prices):
            
            if min_v > price and price != prices[-1]:
                min_v = price
                min_index = index
        print(min_v)

        max_v = prices[min_index]
        for i in range(min_index + 1, len(prices)):
            # print(prices[i])
            if max_v < prices[i]:
                max_v = prices[i]
        print(max_v)

        return max_v - min_v

* 점화식을 생각하지 않고 풀었던 방법임

 

* 단점은 그리디 때 체감했던것 같이, 다른 경우의 수 간에 최선을 파악하기 어려움

 

 

- 두번째 시도

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        
        profit = [0] * len(prices)
        
        for i in range(len(prices)):
            profit[i] = max(prices[i:]) - prices[i] #점화식 도출
        
        return max(profit)

* 각 경우의 수 마다 최대의 이익 구간에서 각 날짜마다 구매 한 날의 차를 구했음

=> 하지만 시간경과로 실패함

 

* max(prices[i:] 이 부분이 O(n^2) 으로 매우 큰 시간복잡도를 가지고 있음

 

 

- 세번째 시도

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        
        if not prices:
            return 0
        
        n = len(prices)
        max_price = [0] * n
        max_profit = 0

        max_price[-1] = prices[-1]
        
        # right to left
        for i in range(n-2, -1, -1):
        	# 끝에서 부터 최댓값 찾아서 저장
            max_price[i] = max(max_price[i+1], prices[i]) 

        print(max_price)
        
        # left to right
        for i in range(n):
            max_profit = max(max_price[i] - prices[i], max_profit)
        
        return max_profit

 

* 매번 리스트에 대해서 슬라이싱대신에, 끝에서 뒤로 오면서 그 값중 최대의 값을 저장하는 방식으로 변경함

=> 이 방식으로 성공적으로 통과함

 

* 하지만 DP, 선형스캔과 취지는 부합하지 않음

=> max_price 리스트에 미리 계산하는 방식은 비효율적

=> 즉 선형 스캔으로 최소값을 추적하면서 최대 이익을 찾는 방식 이 바람직함

 

 

 

<모범 사례>

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        min_price = float('inf')
        max_profit = 0
        
        for price in prices:
            if price < min_price:
                min_price = price
            elif price - min_price > max_profit:
                max_profit = price - min_price
                
        return max_profit

- Linear Scan 방식

리스트를 한번만 순회하여 필요한 계산 완료하는 방법임

 

- 목적

각 요소 한번만 검토하므로 O(n)임

주로 최댓값, 최솟값 찾기 / 누적합 계산에 쓰임

 

- 코드

min_pirce 는 순회 중 탐색된 주식의 최저 가격을 유지함

max_profit 은 구매날 부터 판매 날 까지의 최대 이익 갱신함

 

 

<보충학습>

1. 실무에서 쓰이는 경우

- 재고관리할 때 원재료의 최적 구매 시점 결정함

- 주식/외환에서 최적 매수/매도 시점 적용