[LeetCode]Best Time to Buy and Sell Stock II

언제쯤 다른 사람의 풀이에서 힌트를 얻지 않고 문제를 풀 수 있을까.

 

문제 :

이번 문제의 key point는 

1. 주식을 당일 사고 팔 수 있다. 

2. 꼭 한 번만 팔아서 이윤(profit)을 남길 필요가 없다.

(다음날보다 1원이라도 저렴하면 사서 판다) 

 

풀이 : 

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    var cheapDay = prices.indexOf(Math.min(...prices));
    var lastIdx = prices.length;
    var availableDay = prices.slice(cheapDay,lastIdx)
    var expensiveDay = prices.indexOf(Math.max(...availableDay));
    var profit = 0;
    
    // 가장 저렴한 날이 마지막 날인 경우 
    if (cheapDay == lastIdx) { 
        profit = 0;
    } 
    
    // 가장 비싼 날이 마지막 날인 경우 저렴한 날 구매해 마지막 날에 판매
    if (expensiveDay == lastIdx) { 
       profit = prices[expensiveDay] - prices[cheapDay];
    } 
    
    // 전날보다 금액이 비싼 경우 계속 팔아 이윤을 누적
    for (i = 1; i <prices.length; i++) {
       if (prices[i] > prices[i-1]) {
           profit += prices[i] - prices[i-1]
       }
    }
    return profit
};

rumtime : 53 ms

 

처음에는 profit을 합산을 한다는 생각을 전혀 하지 못해서 가장 저렴한날과 그 이후 날 중 가장 비싸게 팔 수 있는 날을 구해야한다고 생각했다. 그래서 param으로 받은 배열에서 가장 저렴하게 구매할 수 있는 날`cheapDay`을 구해 그 이후의 날`availableDay`들 중 가장 비싼 날`expensiveDay`를 구하여 계산을 해주어야 한다고 생각했다. 

 

하지만, 굳이 변수를 할당해 CASE를 나눌 필요가 없다.

LeetCode에서 예시로 제공한 price `[1,2,3,4,5]`를 보면

i ) `price[0]`에서 구매 후 `price[4]`에서 판매 : 5 - 1 = 4

ii ) `price[0]`에서 구매 후 `price[1]`에서 판매 : 2 - 1 = 1

    `price[1]`에서 구매 후 `price[2]`에서 판매 :  3 - 2 = 1

    `price[2]`에서 구매 후 `price[3]`에서 판매 :  4 - 3 = 1

    `price[3]`에서 구매 후 `price[4]`에서 판매 :  5 - 4 = 1

    이윤의 합산은 i와 동일하게 4가 된다. 

 

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

    let maxProfit = 0;

    for (let i = 1; i < prices.length; i++) {
        let profit = prices[i] - prices[i - 1];
        if (profit > 0) { 
            maxProfit += profit;
        }
    }

    return maxProfit;

};

따라서 이 문제는 여러 고민 없이 `탐욕법(Greedy)`로 풀었으면 충분했던 문제

 

  그래도 아~주 나쁜 수준은 아니다.