[Leet Code풀이] 122. Best Time to Buy and Sell Stock II

문제 설명

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

주식에서 샀다 팔았다 해서 최고 수익이 얼마나 날 수 있는지를 계산한다. Best Time to Buy and Sell Stock와 다른점이 있다면 이 문제는 살다 팔았다는 여러번 할 수 있다는 것이다.

풀이

접근 방법.

이 문제는 리스트를 그래프로 표시해보면 쉽게 풀 수 있다. 이를 주식 그래프처럼 나타내보면 위 처럼 변곡이 일어나는 부분을 캐치해서 누적합을 더해주면 된다.

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        low = prices[0]     # 첫 번째 가격을 최저 가격으로 설정
        before = prices[0]     # 직전 가격 초기화
        acc = 0             # 누적 이익 초기화

        # prices를 반복
        for v in prices:
            #현재 가격이 직전 가격보다 크거나 같은 경우에는 계속 진행합니다.
            if before <= v:
                before = v
                continue

            #현재 가격이 직전 가격보다 작은 경우에는 현재까지의 이익을 갱신하고 최저 가격과 직전 가격을 현재 가격으로 업데이트합니다.
            acc += before - low
            before = low = v
        acc += before - low
        return acc

위 풀이의 시간 복잡도와 공간복잡도는 아래와 같다.

• 시간 복잡도 : O(N) nums만큼 루프를 도므로 O(N)

• 공간 복잡도 : O(1) 추가적인 공간을 사용하지 않는다.