배열 : 주식을 사고 팔기 가장 좋은 시점(리트코드 121번)

▶ 문제 : https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

Best Time to Buy and Sell Stock - LeetCode

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

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

##### 출력 #####
# 5

 

▶ 접근 방법

1) 브루트 포스로 계산
사고 팔고를 반복하면서 최대 이익을 갱신하면 된다. 
다만, 계산 속도가 너무 느리다.

2) 저점과 현재 값과의 차이 계산
입력 값을 확인하면서 최소 값을 갱신하고, 
이후 최소 값과 입력 값의 차이를 계산해서 최대 이익을 갱신한다.

 

▶ 풀이 코드

prices = [7, 1, 5, 3, 6, 4]

def max_profit(prices: list) -> int:
    profit = 0

    for i, price in enumerate(prices):
        for j in range(i, len(prices)):
            profit = max(prices[j] - price, profit)

    return profit

print(max_profit(prices))

def max_profit2(prices: list) -> int :
    profit = 0
    min_profit = float('inf')

    for price in prices:
        min_profit = min(min_profit, price)
        profit = max(profit, price - min_profit)
        
    return profit

print(max_profit2(prices))

 

▶ 관련 링크

2022.01.30 - [알고리즘/리트코드] - 배열 : 세 수의 합(리트코드 15번)