[LeetCode] 121. Best Time to Buy and Sell Stock - 자바스크립트

[ 문제 ]

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

Best Time to Buy and Sell Stock - LeetCode

---

[ 아이디어 ]

동적계획법, DP에 대한 문제였습니다. easy 문제답게 DP에서 메모리제이션 기법을 활용해서 문제를 풀 수 있었습니다.

Discuss 를 보면 이 문제는 DP가 아니라는 말도 보이지만 기본적인 DP를 설명하기에 좋은 문제가 아닐까 개인적으로 생각합니다.

daliyMaxProfitArray에 각 길이별로 가장 이익이 높은 값을 넣고 currentMin을 찾아서 매번 비교하여 주는 코드입니다.

[ 코드 ]

var maxProfit = function (prices) {
    if (prices.length < 2) return 0; //2일보다 작으면 팔수가 없으므로 return 0
    let profit = 0; 

    let daliyMaxProfitArray = [0, prices[1] - prices[0]]; // 일별 최대 수익을 저장할 Array
    let currentMin = prices[1] > prices[0] ? prices[0] : prices[1]; // 이전 날짜까지 가장 싼날

    for (let i = 2; i < prices.length; i++) { // 2일째부터 loop 시작
        daliyMaxProfitArray.push(prices[i] - currentMin); //오늘 가격으로 팔때 가능한 최대 이득
        if (currentMin > prices[i]) currentMin = prices[i]; //가장 싼 가격 업데이트
    }
    profit = Math.max(...daliyMaxProfitArray); // 배열에서 가장 큰 값을 가져와 비교
    if (profit <= 0) return 0;
    return profit;
};

[ 다른 코드 ]

var maxProfit = function (prices) {
    let result = 0;
    let min = prices[0];
    for (let i = 1; i < prices.length; i++) {
        min = Math.min(prices[i], min);
        result = Math.max(result, prices[i] - min);
    }
    return result;
};

로직이 뛰어나다기 보다는 가장 깔끔하게 되어 있어서 가져와봤습니다.