[코딩/LeetCode150-(8)] Best Time to Buy and Sell Stock II (122)

 

본 글은 LeetCode Top Interview 150에 정리된 문제를 요약하고 이에 대한 개인적인 풀이를 포함하고있습니다.
본 포스팅 시리즈는 150 list의 순서를 따라서 게재됩니다. 풀이 언어는 python을 사용합니다.

 

 

 

난이도: Medium

키워드: Array, Greedy

 

문제

 

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

 

prices라는 배열이 주어진다고하자. 이 배열의 i번째 원소들은 주식의 가격을 의미한다. 한 번에 하나의 주식만 가지고 있을 수 있다. 단, 주식을 팔자마자 당일에 바로 살 수 있다.

이러한 조건 하에서 최대 수익(profit)을 찾아서 반환하라.

 

예제 입력

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

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.

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: There is no way to make a positive profit, so we never buy the stock to achieve the maximum profit of 0.

 

풀이

 

처음에는 Dynamic Programming을 사용해서 문제를 풀까 생각했다. 내가 현재 어떤 주식을 살지 말지가 전체 profit의 최댓값의 결정에 영향을 미치기 때문이다. 그런데 조금 더 생각해보면 '주식을 팔고 당일에 살 수 있다'는 조건때문에 Greedy로 문제를 풀 수 있다는 것을 알 수 있다. 최대한 적은 값으로 매입해서 최대한의 금액에 매도하기를 반복하면된다. 따라서 나의 매도 결정이 전역적인 최댓값의 결정에 영향을 미치지 않는다. 따라서 이 코드는 앞선  121번 문제의 코드를 약간만 수정해서 해결할 수 있다.

 

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

        min_val = max_val = prices[0]
        ans = 0
        for price in prices:
            if price > max_val:
                max_val = price
            else:
                ans += max_val - min_val
                max_val = min_val = price
        
        return ans + max_val - min_val

 

 

Takeaway

처음에 DP로 풀려고했는데 state variable을 두개로 가져가면서 search space가 커지고 pruning에 한계가 있어서 메모리 부족으로 다시 문제를 분석했다. 처음 문제를 분석할 때 조건과 이해를 정확히 하는 게 필요하다. 그리고 특히 Greedy를 쓸때는 local optimal이 global optimal인지 확인하는 절차를 꼭 확인하자.

 

 

📚 LeetCode 75 / Code Signal 풀이 보러가기