[Leetcode] 121. Best Time to Buy and Sell Stock (python)

#1.  문제

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

Best Time to Buy and Sell Stock - LeetCode

 

 

 

주식 가격 정보가 담긴 정수 리스트 prices에서 주식을 특정한 날에 사서 이후 다른 날짜의 가격으로 팔아 수익을 극대화할 수 있는 알고리즘을 도출하는 것이 문제의 요구 사항이다.

prices의 인덱스는 날짜를 의미한다.

 

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

# output
Output: 5

# explanation
2번째 날 (idx=1) 가격 1에 구매하여 5번째 날 (idx=4)에 팔면 수익이 5로 가장 크다.

 

---

#2.  풀이

 

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

        for i in range(len(prices)):
            if i == 0:
                min_price = prices[i]
                continue

            if prices[i] < min_price:
                min_price = prices[i]

            else:
                profit = max(profit, prices[i] - min_price)

        return profit

 

최저점에서 최고점에 파는 것이 진리다.

리스트를 순회하면서 최저 가격을 설정하고, 최저 가격보다 큰 값들과의 마진에서 가장 큰 값이 곧 이익을 극대화하는 부분이다.

 

첫날에는 (i == 0) 주식을 사는 행위만 가능하므로 비교를 위한 최저 가격으로 설정해준다.

시간복잡도는 O(N), 파이썬의 max 메서드의 경우 비교 값으로 iterable 객체가 들어갈 경우 리스트 값들을 하나씩 조회해야 하기 때문에 O(N)의 비용이 들지만, 두 수를 비교하는 경우에는 O(1)이다.