[DSA][Two Pointers] 06. Best Time to Buy and Sell Stock

LeetCode 121

 

06. 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.

 

 

[질문하기]

- 주식을 여러 번 사고팔 수 있나요, 아니면 딱 한 번만 거래해야 하나요?

- 같은 날에 사서 같은 날에 팔 수 있나요? NO

- 가격이 음수인 경우도 있나요? NO

 

 

[아이디어]

- 두 개의 포인터 L, R을 사용하여 Profit을 구하다가 Profit이 음수가 되는 시점에 L 포인터를 교체하자.

 

 

[풀이 1] Two Pointer

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        L, R, maxP = 0, 0, 0
        while R < len(prices):
            if prices[R] - prices[L] < 0:
                L = R
            else:
                maxP = max(maxP, prices[R] - prices[L])
            R += 1
        
        return maxP

max profit을 내기 위해서는 가장 저렴한 가격에 주식을 사고, 그 이후 시점 중 가장 비싼 가격에 팔아야 한다.

이를 위해 주식을 사는 시점 L (기준점), 주식을 파는 시점 R (탐색) 이렇게 두 개의 포인터를 사용할 수 있다.

 

R 포인터를 오른쪽으로 이동시키면서 prices[R] - prices[L]를 계산해 현재 이익을 구하는데, 이 값이 음수가 되면 R 시점에서의 가격이 더 낮다는 뜻이므로, 더 나은 구매 시점이 발견된 것으로 간주하고 L = R로 갱신한다. 그렇지 않다면, 현재 이익이 이전 최대 이익보다 큰지 비교하고 maxProfit을 업데이트한다.

 

⏱️ 시간복잡도

배열을 한 번 순회하기 때문에 O(n)의 시간 복잡도를 갖는다.

🧠 공간복잡도

변수 공간만 필요하므로 O(1)의 공간 복잡도를 갖는다.