78. Best Time to Buy and Sell Stock II

리트코드

• 여러 번의 거래로 낼 수 있는 최대 이익을 산출하라.

1. 그리디 알고리즘 (76ms)

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        result = 0
        
        #값이 오르는 경우 매번 그리디 계산
        for i in range(len(prices) - 1):
            if i in range(len(prices) - 1):
                if prices[i + 1] > prices[i]:
                    result += prices[i + 1] - prices[i]
        return result
        

• 12번 '주식을 사고팔기 좋은 시점' 문제의 2탄 격인 문제로, 한 번이 아닌 여러 번의 거래를 할 수 있다는 차이가 있다.
  
  • 이 문제는 단 한 번의 거래였기 때문에 저점과 고점에만 체크했다.

• 이제는 여러번 거래를 할 수 있다.

  • 해법은 내리기 전에 팔고, 오르기 전에 사면 된다.

  • 현실에서는 불가능하겠지만, 이 문제에서는 다음번의 등락 여부를 미리 알 수 있고, 수수료도 없기 때문에 몇 번이든 거래가 가능하다.

    • '탐욕'이라는 의미에 잘 어울리는 그리디 알고리즘 문제라 할 수 있다.

<여러 번 거래가 가능할 때 최대 이익>

• 다음번 값이 오르면 사고, 다음번 값이 내리면 파는, 항상 그리디하게 사고파는 형태로 그림을 변경했다.

  • 다음번 값이 현재보다 오르는 경우에 항상 이익을 취하는 형태로, 실제 코드를 구현하면 될 것 같다.

• 계속 오르는 경우라도 몇 번이든 사고팔 수 있기 때문에, 매번 단계마다 이익을 취하는 탐욕 구조로 구현할 수 있다.

2. 파이썬다운 방식 (72ms)

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        #0보다 크면 무조건 합산
        return sum(max(prices[i + 1] - prices[i], 0) for i in range(len(prices) - 1))
       
        

• 이전 풀이에서 단계별로 값이 올랐는지 가격을 매번 비교하는 방식으로 풀이했다.

• 그런데, 어차피 곰곰히 생각해보면, 매번 이익을 계산해 0보다 크면 무조건 합산할 수 있다.

  • 마찬가지로 탐욕구조며, 동일한 결과를 얻을 수 있다.