121. Best Time to Buy and Sell Stock

문제 개요

• 문제는 간단합니다. 날마다 주식의 가격이 주어지고 가장 큰 수익을 반환하면 됩니다.

• prices = [7, 1, 5, 3, 6, 4] 이렇게 있다면 2번 째 날의 1에서 사고 5번째 날의 6에서 팔면 가장 큰 수익을 얻을 수 있겠네요.

풀이 구상

• 두 가지 값을 계속 비교해나가야 하니 투포인터로 접근해야할 것 같습니다.

• 사는 날과 파는 날의 조건을 다 정해 모든 원소들의 값을 비교 한다면 어렵지 않게 답이 나올 것 같습니다.

• NeetCode에는 이 문제가 Sliding Window로 분류되어 있네요.

• 가변적으로 탐색하는 window가 변하는 유형입니다.

문제해결 코드

class Solution:
    def maxProfit(self, prices: List[int]) -> int:        
        # 배열의 길이가 1개인 경우: 똑같은 가격에 오늘 사서 오늘 파는 경우 => 0

        # 접근 주의사항: profit이 나는 경우를 먼저 생각하기, non-profit을 먼저 고려하면 분기문이 많아짐.
        
        l, r = 0, 1
        maxProfit = 0
        while r < len(prices):
            if prices[l] < prices[r]:
                maxProfit = max(maxProfit, prices[r] - prices[l])
            else:
                l = r
            r += 1
        return maxProfit

• 시간 복잡도는 모든 배열을 돌면서 탐색해서 O(n)입니다.