[Q. 12] 주식을 사고팔기 가장 좋은 시점

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

 

구하는 방법은 간단하다. 저점에 사서 고점에 파는 것이다. 가장 쉽게 구하는 방법은 현재 시점에서 가장 높게 팔 수 있는 가격과의 차이를 구하여 비교하는 방법인데 이 방법은 n의 제곱으로 매우 오래 걸린다.

이를 O(n)에 해결하기 위해 저점을 구한 후, 가격차이 값을 갱신해 가며 max 값을 구하는 방식으로 해결한다.

 

먼저, 저점과 이익의 값을 초기화 한다.

min_price = sys.maxsize
profit = 0

 

그 다음 price 값을 살펴보며, 저점을 설정하고 저점과 현재 가격의 차이를 비교하여 최대 이익을 갱신한다.

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

 

전체 코드는 다음과 같다.

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

        min_price = sys.maxsize
        profit = 0

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

        return profit