JavaScript LeetCode 주식 매수 및 매도 최적기

즉각적인

price[i]가 i번째 날의 주어진 주식 가격인 배열 price가 주어집니다.

특정 주식을 매수하기 위해 하루를 선택하고 해당 주식을 매도하기 위해 미래의 다른 날을 선택하여 이익을 극대화하려고 합니다.

이 트랜잭션에서 얻을 수 있는 최대 이익을 반환합니다. 이익을 얻을 수 없으면 0을 반환합니다.

예 1:

Input: prices = [7,1,5,3,6,4] 
Output: 5 Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5. Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

문제 분석

이전 문제와 마찬가지로 첫 번째 명백한 해결책은 무차별 대입 솔루션을 사용하는 것입니다. 여기서 우리는 배열을 두 번 반복하여 모든 후속 값 사이의 모든 빼기를 확인하고 가장 높은 이익을 얻습니다.

이에 대한 시각적 예는 다음과 같습니다.

첫 번째 솔루션

계속해서 위에서 언급한 코드를 작성해 보겠습니다.

function maxProfit(prices) {
  let profit = 0;
  for (let i = 0; i < prices.length - 1; i++) {
    for (let j = i + 1; j < prices.length; j++) {
      const currentProfit = prices[j] - prices[i]

if (currentProfit > profit ) {
        profit = currentProfit
      }
    }
  }

return profit;
}

여기서 배열의 다음 요소 가격을 현재와 비교합니다. 이것을 개념화하는 가장 좋은 방법은 i가 인덱스이고 j가 계속 반복되는 포인터라는 것입니다.

최대 이익을 찾기 위해 두 개의 for 루프를 사용합니다. 복잡도는 O(n^2)입니다. 이것은 매우 느리기 때문에 꽤 큰 문제입니다! 그러나 어레이를 한 번만 반복하여 이를 최적화할 수 있습니다.

두 번째 솔루션

그러나 단일 반복은 어떤 모습일까요?

코드를 사용하면 다음과 같이 표시됩니다.

var maxProfit = function(prices) {
    let profit = 0;

let stockToBuy = prices[0];

for(let i = 1; i < prices.length; i++) {
        if (stockToBuy > prices[i]) {
            stockToBuy = prices[i]
        }

const currentProfit = prices[i] - stockToBuy;

if (currentProfit > profit) {
            profit = currentProfit;
        }
    }

return profit;
};

배열의 첫 번째 요소에서 초기 stockToBuy를 가져옵니다. 그런 다음 배열에 대한 반복을 시작할 수 있습니다(첫 번째는 건너뛰기). 다음 주식이 현재 선택한 주식보다 가격이 높은지 비교합니다. 그렇다면 더 높은 수익을 올릴 수 있으므로 전환합니다.

그러나 이는 재설정 메커니즘으로도 사용됩니다. 주식의 가치가 더 높으면 이 시점부터 이전에 선택한 주식보다 이익이 더 높지 않을 것임을 알고 있습니다.

stockToBuy = prices[i]

그런 다음 새 currentProfit을 계산합니다. 이는 현재 반복의 임시 값일 뿐입니다.

const currentProfit = prices[i] - stockToBuy;

그런 다음 for 루프 외부에서 저장한 값과 비교합니다. 더 높으면 정확히 우리가 원하는 것입니다.

처음에 0으로 변수를 생성하여 이익을 찾지 못하면 그대로 반환할 수 있습니다.

그리디 알고리즘

근데 이게 뭐라고 불러?

여기서 우리가 하고 있는 것은 모든 반복에서 최선의 옵션을 선택하고 과거 선택은 잊어버리는 것입니다. 이것을 욕심쟁이 알고리즘이라고 합니다.

여기에 대해 더 자세히 알고 싶다면 Wikipedia article이 있습니다.

연결하자

이 내용이 마음에 드셨다면 언제든지 저에게 연락하거나

내newsletter에서 내 무료 개발자 로드맵과 주간 기술 산업 뉴스를 확인하십시오.