121. Best Time to Buy and Sell Stock II

문제 링크: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/

주어진 조건

• prices: 해당 날짜의 특정 주식 가격을 나타내는 정수 배열

문제

• 수익을 극대화할 수 있도록 주식을 특정 날짜에 매수하고, 매도하려고 한다
• 주식은 최대 한 개만 들고 있을 수 있다. (사고, 팔고 여러 번 반복 가능)
• 이때 달성할 수 있는 최대 수익을 return 하자

---

나의 풀이

정말 이리저리 고민을 해보다가, 사실 최대 수익을 얻는 건, 다음 날 가격이 올라간다면, 그 날 매수하고, 다음 날 바로바로 파는 방식이지 않을까 생각이 들어서 아래와 같이 구현했다.

구현 코드

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit = 0
        
        for i in range(1, len(prices)):
            if prices[i] > prices[i - 1]:
                profit += prices[i] - prices[i - 1]
        
        return profit

• prices 배열의 요소를 for문을 통해 반복
• 만약 현재 값보다 이전 값이 작다면, 전체 수익에 현재 값과 이전 값의 차이를 더한다.
• 그렇게 해서 나온 profit을 return

Time: O(N)

for문 하나만 반복하고 있으니, 시간복잡도는 O(N)

Space: O(1)

따로 메모리 공간을 사용하고 있지 않으니, 공간복잡도는 O(1)

위 사진을 보면 그때그때의 저점과 고점에 매수, 매도를 하는 것이 좋다는 것을 알 수 있다.

전역 관점에서봤을 땐, valley2가 최저점, peak5가 최고점이지만 A+B ≥ C 가 성립하는 걸 볼 수 있다.

이 사진도 마찬가지로, valley3가 최저점, peak6이 최고점이지만, 바로 사고 바로 파는 방식을 따랐을 때와 수익이 같다는 것을 알 수 있다.

(A+B+C = D)

---

다른 풀이

class Solution:
    def maxProfit(self, P: List[int]) -> int:
        return sum(P[i]-P[i-1] if P[i] > P[i-1] else 0 for i in range(1, len(P)))

내가 작성했던 코드를 위처럼 짧게 줄일 수 있었다.

아무래도 이 문제의 집중해야 될 포인트는 주식을 산 당일에 다시 살 수 있다는 점이었다.