[LeetCode] 121. 주식을 사고팔기 좋은 시점(Best Time to Buy and Sell Stock

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

 

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.

 

 

 

 

 

 

1. 내가 직접 푼 코드

 

 

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        max_profit = []
        for i in range(len(prices)-1):
            max_profit.append(max(prices[i+1:]) - prices[i])
        print(max_profit)
        return max(max_profit)

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit = 0
        min_price = sys.maxsize
 
        # 최솟값과 최댓값을 계속 갱신
        for price in prices:
            min_price = min(min_price, price)
            profit = max(profit, price - min_price)
 
        return profit

해설:

 

 

for문으로 진행하면서 최솟값이 되는 가격을 따로 저장해 두고

최소 가격과 현재 가격 간의 차이에 max를 취해 profit에 저장한다.

이런 식으로 하면 O(n)에 해결할 수 있어서 런타임 에러가 뜨지 않는다!

 

 

 

만약 쉽게 알고리즘이 떠오르지 않는다면 그래프로 한 번 그려보자.

값을 시각화해보면 어떤 식으로 풀어야 할지 직관이 생긴다고 한다.

 

 

 

 

출처 : 파이썬 알고리즘 인터뷰 (글 : 박상길 그림 : 정진호) [책만]