Best Time to Buy and Sell Stock

Best Time to Buy and Sell Stock

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/?envType=study-plan-v2&envId=top-interview-150

문제 요약

• 주식의 가격이 담긴 prices 배열이 주어짐
• 현재 i보다 앞선 가격에서는 매매 불가능, i + 1 부터 매매 가능
• return 최대 이익 계산 if 계산 가능 else 0

풀이

• prices 배열의 길이는 100,000 최대 O(nlogn) 풀이까지 가능
• 모든 날에서 사고 파는 것이 아닌, 한번에 대하여 최대 이익을 구하는 것
• 최대 이익 = 미래의 가장 비싼 가격 - 과거의 가장 싸게 산 가격
• 따라서, 가장 싼 가격을 저장해두고 최대 이익을 계산해 나간다.

수도 코드

def sol(prices):
	최소 가격 = prices의 첫째 값
    최대 이익 = 0
    
    for price in prices:
    	최소 가격 = min(최소 가격, price)
        최대 이익 = max(최대 이익, price - 최소 가격)
        
    return 최대 이익

Solution(Runtime: 765ms)

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        max_prf, min_price = 0, prices[0]
    
        for price in prices:
            if min_price > price:
                min_price = price
            if max_prf < price - min_price:
                max_prf = price - min_price
        
        return max_prf

다른 사람의 코드를 읽으며 투포인터 방식으로도 풀이가 가능하다는 것을 알게 되었다.

투포인터 방식(Runtime: 887ms)

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
    	# left에서 사고 right에서 팔기
        L = max_prf = 0
        R = 1

        while R < len(prices):
        	profit = prices[R] - prices[L]
            max_prf = max(max_prf, profit)

            if profit <= 0:
                L = R
            R += 1
        
        return max_prf

L 포인터를 어떤 경우에 증가시켜야할지 고민이 많았다. profit이 0보다 작거나 같을 때 L을 R로 이동시켜 주었다. 그 이유는 항상 이익을 얻어야 하며 얻지 못한 경우는 0을 리턴하도록 되어 있다. 즉, 손해를 보면서 매매를 하는 경우는 허용하지 않는다라는 말이기 때문이다. 또한 R이 가리키는 값이 현재보다 더 작은 값이므로 현재보다 큰 profit을 얻을 수 있을 것이다.