[LeetCode] - 주식을 사고팔기 가장 좋은 시점

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

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

Best Time to Buy and Sell Stock - LeetCode

 

▶ 입력 

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

▶ 출력

5 

 

1일 때 사서 6일 때 파는 것이 가장 큰 이익을 얻는다. 

---

풀이) 

1. 브루트 포스 

만일 첫째 날인 7일때 샀을 경우, 나올 수 있는 이익은 다음과 같다.

 

두번째 날  팔 경우 : 1-7 = - 6 ,

세번째 날 팔 경우 : 5-7 = -2 ,

네번째 날 팔 경우 : 3-7 = -4,

다섯번째 날 팔 경우 : 6-7 = -1 ,

여섯번째 날 팔 경우 : 4-7 = -3 

 

이런 식으로 모든 경우의 수를 구하여 최대 이익을 계산해보자.

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

        max_price = 0 

        for i , price in enumerate(prices) :
            for j in range(i+1 , len(prices)) :
                max_price = max(max_price , prices[j] - price)
        
        return max_price

 

하지만 이와 같이 브루트포스로 풀이하게 되면 time error가 발생한다.  

2. 저점과 현재값 차이의 계산 

시각화하여 한 번 살펴보자

현재값이 우측으로 이동하면서 저점과 차이를 계산하여 최대 이익을 산출해 낼 수 있다. 

따라서 현재값 - 최저점 차이를 계산하여 계속해서 최대값을 갱신하여 풀이하면 시간 복잡도를 줄일 수 있다. 

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

        max_price = 0
        min_price = sys.maxsize

        for i , price in enumerate(prices) :
            min_price = min(min_price , price)
            max_price = max(max_price , price - min_price)
        
        return max_price

---

 

💡최댓값과 최솟값의 초깃값을 설정하는 것도 따로 기록해두었다. 

https://zzoming00.tistory.com/56

 

파이썬 - 최댓값과 최솟값의 초깃값 설정