leetcode 121 - Best Time to Buy and Sell Stock

 

 

하루에 한번 매매를 할 수 있을 때, 어떻게 하면 저점에 사서, 고점에 팔 수 있는 알고리즘을 짜는 것이다.

for loop를 두번 도는 것이 아닌, 매 loop를 돌 때마다 최고 가격과 최저가격을 기록하면 되는 것이므로, 아래와 같이 그냥 O(n)으로도 풀이가 가능하다.

 

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        import sys
        
        profit = 0
        min_price = sys.maxsize
        
                
        for price in prices:
            if price < min_price:
                min_price = price
            
            if price - min_price > profit :
                profit = price - min_price            

        # print(profit)
        return profit

풀이 과정을 본다면, 먼저 profit은 0라고 가정하고, min_price는 system에서 허용가능한 최대수를 가정한다.

 

그리고 for loop을 돌면서 가장 낮은 가격(min_price)을 매 loop마다 갱신하며, 이 저장된 min_price와 현재 price와 계산한 profit이 이전에 계산했던 profit보다 높다면, profit을 갱신시킨다.

 

이렇게 매 loop마다 나온 결과를 따져보면 최대 profit을 얻을 수 있다