[LeetCode] Best Time to Buy and Self Stock

 

문제

You are given an array prices where prices[i] is the price of a given stock on the ith day.
You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.
Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

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.

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.

 

접근 방법

이중 for문을 써서 풀려고 했지만 웬지 이 방법이 더 복잡했다. for문 돌리면서 최소값을 계속 갱신해주고 for문 원소에서 이 최소값을 계속 뺴주면 이익금이 나올꺼고 이 중에서 최대값을 뽑아서 return하면 되지 않을까?

 

Code

def maxProfit(self, prices: List[int]) -> int:
    money = 999999
    max_value = 0
    for idx, value in enumerate(prices):
        money = min(money, value)  # 최소값 갱신함

        profit = value - money  # 이익금 = 원소 - 최소값

        max_value = max(max_value, profit)  # 최대값(원소에서 - 최소값)으로 갱신

    return max_value

코드를 작성 해놓고 보니 말로만 써놨던 접근 방법보다 훨씬 이해가 잘 되는 것 같다. 근데 결과를 보니 웬지 효율이 나빠보이는 것 같다.

 

개선?

개선이랄 것 까지는 없지만서도 하나씩 뜯어보자. 눈에 보이듯이 enumerate를 통해서 뽑아놓은 idx는 안 쓰는 값이다. 그러므로 enumerate 대신 list를 그대로 써도 상관 없을 듯 하다.

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        money = 999999
        max_value = 0
        for value in prices:
            money = min(money, value)  

            profit = value - money  

            max_value = max(max_value, profit)

        return max_value

결과는 Runtime이 훨씬 증가했다.