문제

Best Time to Buy and Sell Stock

문제 설명

입력으로 각 시점에서 주가 배열 prices가 주어진다. 최대 한번의 거래를 통해 얻을 수 있는 최대 이익을 구해야한다. (주식 매수, 매도 1번 씩)

예제

Input: [7,1,5,3,6,4]
Output: 5

prices 배열로 [7,1,5,3,6,4] 값이 주어졌다. 최대 이익을 얻기 위해서는 주가각 1일 때 매수하여 6일 때 매도하면 5의 최대 이익을 얻을 수 있다.

풀이

Brute Force
가장 먼저 생각 난 방법은 그냥 모든 경우에서 얻을 수 있는 이익을 계산하여 그 중 최대값을 얻어냈다. 시간복잡도가 0(n^2)이므로 좋은 방법은 아니다.

const maxProfit = function (prices) {
  let max = 0;
  for (let i = 0; i < prices.length; i++) {
    for (let j = i + 1; j < prices.length; j++) {
      if (prices[j] - prices[i] > 0 && max < prices[j] - prices[i]) {
        max = prices[j] - prices[i];
      }
    }
  }
  return max;
};

---

불필요한 계산을 피하기 위해서 주가의 최소값을 기억하고 다음에 나오는 주가와 비교하여 최소값을 갱신하면서 최대 이익을 얻었다.

const maxProfit = function (prices) {
  let min = prices[0];
  let max_benfit = 0;

  for (let i = 1; i < prices.length; i++) {
    if (min > prices[i]) {
      min = prices[i];
    } else if (max_benfit < prices[i] - min) {
      max_benfit = prices[i] - min;
    }
  }
  return max_benfit;
};

첫 번재 if문을 만족할 경우 최소 주식 매수 가격(최소값)을 갱신한다.
만족하지 않을 경우에는 현재 계산해둔 최대 이익(max_benefit)과 현재 이익(prices[i] - min)
값을 계산하여 최대 이익 값을 갱신하였다.

제출 결과 시간복잡도 O(n)으로 효율적인 코드인것 같다.

---

One Pass

포인트로 생각해야 할 점은 가장 최소 지점과 최소 지점 이후로 나오는 최대 지점의 값을 구하는 것