Python 알고리즘 인터뷰 - 문제12. 주식을 사고팔기 가장 좋은 시점

leetcodee 121. Best Time to Buy and Sell Stock - https://leetcode.com/problems/product-of-array-except-self/

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

 

예제 

입력

[7,1,5,3,6,4]

 

출력

5

 

풀이

prices를 순회하면서 가장 작은 금액을 갱신하며 해당 변수를 min_price라고 한다. 이후 prices의 각 엘리먼트 값 price와 min_price의 차이를 profit이라고 했을 떄 profit의 최대값을 갱신해 나간다. 현재 최소 금액 min_price보다 작은 금액을 만나기 전에는 해당 금액이 최적의 구매 시점이므로, 최대 profit값을 계속 갱신해나가면 된다.

 

min_price보다 작은 price 값을 만나면 해당 값으로 갱신한 후 동일한 연산을 반복한다.

 

코드로 나타내면 다음과 같다.

profit = 0
min_price = prices[0]

for i in range(1, lens(prices)):
	min_price = min(min_price, prices[i])
    profit = max(profit, prices[i] - min_price)

return profit

 

profit, min_price를 각각 0, prices[0]으로 초기화한 후 루프 순회를 진행하는데 코드를 간결하게 하기 위해 다음과 같이 수정이 가능하다.

profit = 0
min_price = sys.maxsize

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

return profit

min_price = sys.maxsize로 수정하였으며 for loop가 for price in prices로 수정되었다. 처음 루프에 진입했을 때 price값은 sys.maxsize보다 항상 작기 때문에 min_price = price이 되어 동일하게 로직이 진행된다.

 

전체코드는 다음과 같다.

def maxProfit(self, prices):
    profit = 0
    min_price = sys.maxsize

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

    return profit