LeetCode 121. Best Time to Buy and Sell Stock

Best Time to Buy and Sell Stock

문제

문제 설명

You are given an array prices where prices[i] is the price of a given stock on the ith day.
You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

그날의 주식 가격이 든 배열 prices가 주어진다.
최대 이익을 남길 수 있는 매수일, 매도일을 정하여 그 최대 이익을 반환하는 문제. 이익을 얻을 수 없다면 0을 반환.

매수 이전엔 매도를 할 수 없다는 게 중요 포인트.

입출력 예

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.

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.

제한 사항

• 1 <= prices.length <= 10^5
• 0 <= prices[i] <= 10^4

풀이

나의 풀이

내게 가장 익숙한 이중 for문으로 풀었더니 시간 초과가 떴다.
배열의 최대 길이가 10^5면, O(n2)의 시간복잡도를 가진 이중 for문은 최대 (10^5)^2번 작동하게 된다. ((10^5)^2 = 100억)

// 1차 풀이: O(n2)
// Rumtime: N/A
// Memory: N/A

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

재도전

최소 금액과 최대 이익을 모두 변수에 저장해두면 반복문을 한 번만 돌아도 된다는 것을 깨달았다.
minPrice는 반복문을 돌면서 더 작은 값이 들어가게 하고, maxProfit은 현재 위치에서 가장 작은 값인 minPrice와 현재 가격 price의 차 중 가장 큰 값으로 계속 업데이트 해준다.

// 2차 풀이: O(n)
// Rumtime: 135 ms
// Memory: 51.9 MB

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

  for (const price of prices) {
    if (minPrice > price) minPrice = price;
    else if (maxProfit < price - minPrice) {
      maxProfit = price - minPrice;
    }
  }

  return maxProfit;
};

다른 사람들의 풀이

Math.max, Math.min 메서드를 사용하여 조금 더 간결하게 작성한 코드를 자바스크립트 문법으로 작성해봤다.
이 메서드들은 배열 내에서 최댓값, 최솟값을 찾을 때 사용하며 익숙해졌기 때문인지 독립적인 요소들을 비교할 때는 잘 떠오르지 않는다.

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

  for (const price of prices) {
    minPrice = Math.min(minPrice, price);
    maxProfit = Math.max(maxProfit, price - minPrice);
  }

  return maxProfit;
};

WIL

Math.max()

Math.max()
Math.max(value0)
Math.max(value0, value1)
Math.max(value0, value1, /* … ,*/ valueN)

1. 독립적인 요소들을 비교할 때도 Math.max(), Math.min()를 사용할 수 있다.
2. 제한사항을 꼼꼼히 보고 시간복잡도를 고려해서 풀자.