[배열] 주식을 사고팔기 가장 좋은 시점

* leetcode 121. Best Time to Buy and Sell Stock

 

Q. 한 번의 거래로 낼 수 있는 최대 이익을 산출하라.

# 입력
[7, 1, 5, 3, 6, 4]

# 출력
5

# 1일 때 사서 6일 때 팔면 최대 5의 이익을 얻는다.

 

풀이 1. 브루트 포스로 계산

# O(n^2)로 사고 팔고를 반복하여 최대 이익을 구한다.
def maxProfit(prices: List[int]) -> int:
    max_price = 0
    
    for i, price in enumerate(prices):
       for j in range(i, len(prices)):
           max_price = max(prices[j] - price, max_price)
    
    return max_price

이 풀이법은 시간 복잡도가 O(n^2)으로 비효율적이다. 따라서 다음 풀이법을 사용해야 한다.

 

풀이 2. 저점과 현재 값과의 차이 계산

def maxProfit(prices: List[int]) -> int:
    profit = 0
    min_price = sys.maxSize
    
    # 최솟값과 최댓값 계속 갱신
    for price in prices:
        min_price = min(min_price, price) # 현재값이 최솟값보다 작으면 최솟값을 갱신
        profit = max(profit, profit - min_price) # 갱신된 최솟값으로 이익 최댓값 갱신
        
    return profit