[리트코드/leetcode/python] 121. Best Time to Buy and Sell Stock

이미지를 누르면 문제 링크를 보실 수 있습니다.

위 문제는 그리디 문제입니다. 

리스트를 순회하면서 최적의 값을 찾아나가는 문제이죠.

맨 처음에 저는 O(n^2))의 복잡도로 문제를 풀었습니다. 그래서, 시간초과의 문제에 걸렸습니다.

제약조건을 보면 prices의 길이가 최대 100000이기 때문에, O(n^2)의 복잡도로 풀어버리면 10의 8승을 넘기 때문에 시간초과에 걸리는 것은 당연한 소리겠죠!

 

처음, 시간초과에 걸렸던 코드는 아래와 같습니다.

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        
        is_reversed_sorted = all(prices[i] >= prices[i+1] for i in range(len(prices)-1))
       
        if is_reversed_sorted:
             return 0

        i = 0
        profit = -10001

        while i < len(prices)-1 :
             for j in range(i+1,len(prices)):
                 if prices[i] < prices[j] :
                     profit = max(profit,prices[j] - prices[i])
             i += 1
             
        return profit

문제를 접근했던 방법은 이렇습니다.

is_reversed_sorted 라는 변수에는 해당 리스트가 오름차순 리스트라면 true를 그렇지 않다면 false를 갖도록 설정했습니다.

빌트인 함수 all은 인자로 주어진 리스트의 모든 요소가 True일때 True를 반환하는 함수 인데요, prices리스트를 돌면서 true나 false를 저장하겠고, 이러한 리스트들이 모두 true라면 오름차순으로 정렬된 것이겠고 아니면 오름차순 리스트가 아니므로 false를 가질 것 입니다.

 

i를 0부터 시작하며 while문을 돌면서 prices를 차례대로 바라보는데, profit 변수를 최대 이익이 나올 수 있도록 계속 갱신해줍니다. 기본적으로 반복문이 2번 쓰였기 때문에 시간복잡도는 O(n^2)이 됩니다.

이 방식은 결국 시간초과를 발생하게 했고, 복잡도를 줄여야했습니다.

 

문제를 보면 반복문을 한번만 쓰더라도 풀 수 있는 방법이 있었는데요,

핵심은 최소값을 찾는 것입니다. 어차피 prices리스트는 각 날짜마다 살 수 있는 가격이 들어가 있기 때문에, 현재 바라보는 날 이후만 생각해도 됩니다.

 

개선된 코드를 한번 살펴볼까요?

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

        minVal = max(prices)
        maxProfit = 0

        for p in prices:
            minVal = min(minVal,p)
            maxProfit = max(maxProfit,p-minVal)
        return maxProfit

minVal 변수에 prices의 최댓값을 할당해주고, 

maxProfit변수에는 0을 할당해준채로 시작합니다.

 

prices리스트를 돌면서 minVal을 갱신해주는데요, minVal을 갱신해야 maxProfit의 값도 변하기 때문입니다.

maxProfit은 (기존 maxProfit)과 (현재바라보고 있는 가격-minVal) 을 비교해서 큰 값을 할당해줍니다.

이러면, 복잡도는 O(n)으로 현저히 줄고 is_reversed_sorted라는 변수를 따로 만들기 위한 순회도 안해줘도 돼요!

 

이상 Best Time to Buy and Sell Stock 문제를 정리해봤습니다.