[알고리즘][Python] LeetCode 121 Best Time to Buy and Sell Stock 문제 풀이

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

Best Time to Buy and Sell Stock - LeetCode

---

문제 해석 : 시간에 흐름에 따라 생성된 배열은 각 시간에 흐름에 따른 주식의 가격을 의미한다. 이때 최대의 이득을 구하여라

 

문제 풀이 : 모든 경우의 수를 검사할 때는 시간 복잡도가 O(N^2)이기 때문에 문제를 풀이할 수 없다. 따라서 O(N)으로 풀이하기 위해서 min_price 변수를 도입하고 이를 활용해서 price들을 검사하는데 있어서 최소값을 업데이트하고 답도 업데이트하는 방식을 사용한다.

---

풀이 코드

import sys
from typing import List


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

        min_price = sys.maxsize

        for price in prices:
            answer = max(answer, price - min_price)

            if price < min_price:
                min_price = price

        return answer

if __name__=="__main__":
    solution = Solution()
    prices1 = [7,1,5,3,6,4]
    prices2 = [2,4,1]
    print(solution.maxProfit(prices1))
    print(solution.maxProfit(prices2))

---

author : donghak park
contact : donghark03@naver.com

## 문제의 저작권은 LeetCode 사이트에 있습니다. 혹시 문제가 되는 부분이 있으면 연락 바랍니다.