[LeetCode | Python] 121. Best Time to Buy and Sell Stock

You are given an array prices where prices[i] is the price of a given stock on the ith day.
You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.
Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

주식 가격 배열이 주어졌을 때, 얻을 수 있는 maximum profit을 리턴하는 문제.

 

풀이1: 브루트포스? - O(n^2)

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        res = 0
        for i in range(len(prices)):
            buy = prices[i]
            for j in range(i+1, len(prices)):
                sell = prices[j]
                res = max(res, sell - buy)
        return res

 

모든 buy와 sell 조합을 비교하여 최대 이익을 찾는다.

이중 반복문으로 물론 리트코드에선 시간 초과가 난다.

 

살짝만 변형하여 아래의 그리디처럼 변경하면 O(n)으로 풀이할 수 있다.

 

풀이2: 그리디  - O(n)

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

        buy = prices[0]
        res = 0

        for p in prices[1:]:
            if buy > p:
                buy = p
            
            res = max(res, p - buy)
        
        return res

 

위처럼 현재까지의 최소 매수 가격을 추적하며, 각 가격에서의 최대 이익을 계산할 수 있다.

그리디 풀이는 단순하고 직관적이지만, 조건이 복잡해지면 적용하기 어려울 수 있다.

 

 

풀이3: Two Pointers (Sliding Window, O(n))

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        l, r = 0, 1
        res = 0
        
        while r < len(prices):
            if prices[l] < prices[r]:
                profit = prices[r] - prices[l]
                res = max(res, profit)
            else:
                l = r
            r += 1

        return res

l 포인터는 최소 매수 가격을, r 포인터는 현재 매도 가격을 가리킨다.

이 두 포인터를 사용해, 배열을 한 번만 순회하면서 윈도우를 슬라이딩하므로 O(n) 시간복잡도를 가진다.

 

슬라이딩 윈도우는 더 일반적인 문제에도 확장 가능하다.

윈도우 크기, 이동 방향, 조건을 유연하게 설정할 수 있기 때문이다.