[파이썬] 리트코드 121. Best Time to Buy and Sell stock 풀이

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

Best Time to Buy and Sell Stock - LeetCode

한 번의 거래의 최대 이익을 구하는 문제다. 따라서 가장 가격이 낮을 때 사서 가장 가격이 높을 때 팔면 된다.

이 역시 시간제한이 존재하기 때문에, 단순히 모든 경우의 수를 탐색하며 풀면 시간초과가 난다 

 

그러므로 반복문을 한 문장으로 만들어줘야 한다 

1. 최소가격을 min_price로, 이익은 profit으로 선언해준다 

2. prices의 요소인 i에 대해서 min_price와 값을 비교하여 작은 것을 min_price로 갱신해준다

3. 이익은 profit 혹은 i에서 min_price를 뺀 값 중 큰 것이 된다 

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        #시간 초과가 나는 예 
        '''max_price = 0 
        for i , price in enumerate(prices):
            for j in range(i,len(prices)):
                max_price = max(prices[j]-price,max_price)
        return(max_price)'''
        
        #시간 초과 해결
        profit = 0 
        min_price = sys.maxsize
        for i in prices:
            min_price = min(min_price,i)
            profit = max(profit,i-min_price)
        return profit

 

<참고>

https://g.co/kgs/AxqygF

파이썬 알고리즘 인터뷰