[LeetCode] 122. Best Time to Buy and Sell Stock II

Best Time to Buy and Sell Stock II - LeetCode

 

바로 이전글에서 풀었던 문제와 같은 주제의 문제입니다.

주식을 사고파는데 수익을 얻을수 있다면 무조건 사고파는 로직을 구현해야합니다.

 

 문제 접근

단순하게 생각했습니다.

만약 지금 바라보는 요소가 이전값보다 크다면?

이전 요소를 사서 이번에 팔았다고 가정했습니다.

    public int maxProfit(int[] prices) {
        int ret = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i-1] < prices[i]) {
                ret += prices[i] - prices[i - 1];
            }
        }
        return ret;
    }

 

시간복잡도

loop문을 1번만 돌고있습니다.

그외에 다른 로직은 없으니 O(n)의 시간복잡도를 사용합니다.

 

다른사람의 풀이

DP를 사용해 푸는 방법입니다. 

이 코드를 정확히 이해하고있는것 같지 않아

정확히 이해하고 수정하겠습니다.

 

public int maxProfit(int[] prices) {
        int n = prices.length;
        int maxProfit[][] = new int[n][2]; 
                                           
        maxProfit[0][0] = 0;  
        maxProfit[0][1] = -prices[0]; 

        for (int i = 1; i < n; i++) {
            maxProfit[i][0] = Math.max(maxProfit[i - 1][0], maxProfit[i - 1][1] + prices[i]);
            
            maxProfit[i][1] = Math.max(maxProfit[i - 1][1], maxProfit[i - 1][0] - prices[i]);
        }
        
        return maxProfit[n - 1][0]; 
    }

 

 

 

느낀점

이번문제는 생각보다 간단하게 푼것같습니다.

어떻게 접근해야할지 다양하게 생각해보면서 문제를 푸는 습관을 가져야겠습니다!