[LeetCode] Best Time to Buy and Sell Stock - Javascript

Best Time to Buy and Sell Stock

[주식 가장 싸게 사서 가장 비싸게 팔기]

제약 조건 

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

Example

ex1) 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.

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

초기 문제 접근 방식

먼저 반복문은 k의 값만큼 순회하고 splice를 사용해 기존의 배열은 유지한 채로,
k 값을 기준으로 해당 위치에 있는 값을 배열의 맨 앞으로 이동시킨다.
그 후 해당 인덱스는 배열에서 삭제하는 방법을 생각했다.

그럼 반복문 i가 0일 땐,
[1,2,3,4,5,6,7] -> [5,1,2,3,4,6,7]으로 변경되며
k를 1씩 감소하며 나머지 뒤에 있는 배열도 앞으로 옮기는 작업을 한 것이다.

초기 전체코드

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
   let max = -1;
   let profit = -1;
   let tmp = {};
   for (let i = 0; i < prices.length; i++) {
      if (tmp.hasOwnProperty(prices[i])) {
         max = tmp[prices[i]];
      } else {
         max = -1;
      }

      for (let j = i + 1; j < prices.length; j++) {
         if (prices[i] < prices[j] && max < prices[j] - prices[i]) {
            max = prices[j] - prices[i];
            tmp[prices[i]] = max;
            console.log(tmp);
         }
      }
   }

   const arr = Object.values(tmp);
   console.log(arr);
   if (arr.length) {
      profit = Math.max(...arr);
      return profit;
   } else {
      return 0;
   }
};

 

해당 코드로 주어진 아래의 testcase 2개를 통과하여 제출을 했다.

ex1) 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.

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

 

 

다시 생각 해보며..

하지만 전체의 212개의 testcase 중 200개밖에 통과를 하지 못했고, 풀이하는데  있어 코드 자체는 문제가 없으나,

타임아웃에 걸려 문제를 못푸는것으로 확인됐다.

아마 이중for문을 사용해서 타임아웃에 걸리는것 같다.

아주 난감했다...

몇시간을 고민해 하나의 for문을 사용해 풀었다.

 

solve 전체 코드

/**
 * @param {number[]} prices
 * @return {number}
 */
const maxProfit = function (prices) {
   let answer = 0;
   let min = prices[0];

   for (let i = 1; i < prices.length; i++) {
      min = Math.min(min, prices[i - 1]);
      answer = Math.max(prices[i] - min, answer);
   }
   return answer;
};

오늘(i)을 기준으로 가장 주식이 저렴했던 날을 min에 저장한다.

그 후 오늘의 주식가격과 가장 저렴했던 주식 min을 빼고 그 값을 이익이 가장 많이 났던 answer와 비교해서 더 큰 값을 answer에 저장한다.

코드는 짧지만, 생각하는 데에 아주 오랜 시간이 걸렸던 문제였다.

 

다른 sovle 코드

많은 풀이들을 찾아봤지만, 내 로직과 거의 비슷한 풀이 방법이 많았다.