[Leet Code Top 100] #121. Best Time to Buy and Sell Stock

문제 정보

• Leet Code 문제 링크
• 난이도 : easy

 

해결 방법

첫 시도에는 단순히 이중 for loop 를 사용하여 O(n^2) 의 시간이 걸리게 구현하니 Time Limit Exceeded 을 판정되었습니다.

두 번째 시도에서는 prices 를 두번 순회하지 않기 위해 고민을 하던 중에 변화량을 기록하는 diff 라는 Array 를 만들고 최대 부분합을 구할 수 있는 Dynamic Programming 을 사용하여 값을 구했습니다. ( 참고로, 최대 부분합을 구하는 이 알고리즘을 카데인 알고리즘이라고 한다고 합니다. 기존 DP 와 내용은 같긴한데... 자주 등장하기 때문에 그런것 같습니다. )

이렇게 풀고 나서 Solution 탭을 확인해보니 for loop 마다 minPrice 와 maxProfit 을 업데이트하며 간단하게 풀 수 있었습니다. 성능은 두 번째 시도에서 했던 DP 와 비슷하지만 소스 길이나 이해하기가 ( 심지어 구현도... ) 훨씬 쉽습니다.

 

소스 코드

// Leet Code
// #121. Best Time to Buy and Sell Stock
// Success
// Runtime: 206 ms, faster than 5.08% of JavaScript online submissions for Best Time to Buy and Sell Stock.
// Memory Usage: 54.6 MB, less than 5.02% of JavaScript online submissions for Best Time to Buy and Sell Stock.

function main(){
    // Input
    prices = [7,6,4,3,4];
    // Output
    // 5
    console.log(maxProfit(prices));
}

/**
 * @param {number[]} prices
 * @return {number}
 */
// var maxProfit = function(prices) {
//     let max = 0;

//     for(let idx = 0; idx < prices.length - 1; idx++){
//         for(let jdx = idx + 1; jdx < prices.length; jdx++){
//             if(max < prices[jdx] - prices[idx]){
//                 max = prices[jdx] - prices[idx];
//             }
//         }    
//     }

//     return max;
// };

// var maxProfit = function(prices) {
//     let max = 0;
//     const diff = new Array(prices.length - 1);
//     // dp[idx] : max sum of diff that idx is right end point 
//     const dp = new Array(prices.length - 1); 

//     // makes 'Maximum Subarray' problem
//     for(let idx = 1; idx < prices.length; idx++){
//         diff[idx - 1] = prices[idx] - prices[idx - 1];
//     }

//     for(let idx = 0; idx < diff.length; idx++){
//         if(0 != idx && dp[idx - 1] + diff[idx] > diff[idx]){
//             dp[idx] = dp[idx - 1] + diff[idx];
//         } else {
//             // start sum from idx
//             dp[idx] = diff[idx];
//         }            
//         //console.log(`diff:${diff[idx]}`);
//     }

//     max = Math.max(...dp);
//     if(max < 0){
//         max = 0;
//     }
//     return max;
// };

var maxProfit = function(prices) {
    let maxProfit = 0;
    let minPrice = prices[0];

    // update maxProfit & minPrice
    for(let idx = 0; idx < prices.length; idx++){
        if(prices[idx] < minPrice){
            minPrice = prices[idx];
        } else if(maxProfit < prices[idx] - minPrice){
            maxProfit = prices[idx] - minPrice;
        }
        //console.log(`minPrice:${minPrice} / maxProfit:${maxProfit}`);        
    }

    return maxProfit;
};

main();

 

참고 자료

• LeetCode Top 100 Problem Selection
• Dynamic Programming - Kadane’s Algorithm (카데인 알고리즘)