[Leetcode] 122. Best Time to Buy and Sell Stock II (python)

#1.  문제

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

Best Time to Buy and Sell Stock II - LeetCode

 

 

 

 

121번 문제의 심화 버전이다.

하루에 보유할 수 있는 최대 주식의 갯수가 1개일 때, 다수의 거래로 발생 가능한 최대 이익을 찾는 문제다.

 

# input
prices = [3,3,5,0,0,3,1,4]

# output
Output: 8

# explanation
idx = 1 가격 3에 구매하여 idx = 2 가격 5에 팔면 수익이 2
idx = 4 가격 0에 구매하여 idx = 5 가격 3에 팔면 수익이 3
idx = 6 가격 1에 구매하여 idx = 7 가격 4에 팔면 수익이 3
총 이익: 8

 

---

#2.  풀이

 

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        import collections

        prices = collections.deque(prices)
        profit = 0

        buy = prices.popleft()
        
        while prices:

            sell = prices.popleft()
            
            if sell > buy:
                profit += (sell - buy)
            
            buy = sell

        return profit

 

예시에 나오는 해설로 인해 쉽게 호도될 수 있는 문제다.

Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Total profit is 4.

 

당장 최적해를 얻을 수 있는 방법(그리디)로 문제를 풀면 쉽게 해결할 수 있다.

한번에 보유 가능한 주식(1개)만 지킨다면 전체 day의 다수의 거래도 상관없기 때문에 이익을 낼 때마다 더해준다.

 

 

시간을 정말 많이 투자한 문제다.

투포인터, 비교, 해시맵등등 아무리 최적화를 하려고 해도  계속 O(N*3)의 시간복잡도가 나왔다.

완성한 알고리즘은 예시를 다 통과해도 정작 몇개의 특수 케이스를 통과하지 못했다.

이것만 해결하면 될 거라는 생각에 매몰되어 시간가는 줄 모르고 계속 시도했지만 쉽지 않았다.

문제를 다시 복기하면서 결국 문제 요구사항을 잘 못 이해하고 있다는 것을 깨달았다.