Time Limit Exceeded 1

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    let maximumProfit = 0;

    for(let i = 0; i < prices.length - 1; i++){
        for(let j = i; j < prices.length; j++){
            // profit이 음수나 0이 나오는 경우는 continue
            if(prices[i] >= prices[j]){
                continue;
            }

            let profit = prices[j] - prices[i];

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

    return maximumProfit;
};

이중 for문을 돌려서인지 테스트 통과가 거의 끝날 즈음에 시간 초과가 되었다.
어떻게 하면 이를 더 간결하게 만들 수 있을까?

Time Limit Exceeded 2

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    let maximumProfit = 0;

    for(let i = 0; i < prices.length; i++){
        const max = Math.max(...prices.slice(i+1));
    
        let profit = max - prices[i];

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

    return maximumProfit;
};

이중 for문을 벗어나기 위해 고안한 방법이다.
기준을 잡고, 그 기준 뒤에 있는 값들 중 가장 큰 값(가장 큰 이익을 내기 위해)을 잡고
그 차이를 계산해 이익을 구한 뒤, 지금까지 구해온 최대 이익과 비교하여 더 높은 값을 얻는 방법이다.
그러나 이 방법 또한 시간 초과가 되었다.
이번에 의심되는 부분은 Math.max(...prices.slice(i+1)) 부분이다.
매 순회마다 slice()와 스프레드 연산자를 사용하는 탓이 아닐까?

solution

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    if(prices.length === 1){
        return 0;
    }

    let min = prices[0];
    let max_diff = 0;
    
    for(let i=1; i<prices.length; i++){
        if(prices[i] < min){
            min = prices[i];
            continue;
        }
        
        let diff = prices[i] - min;

        if(diff > max_diff){
            max_diff = diff;
        }
    }

    return max_diff;
};

이번에는 최대 이익을 내기 위한 최대값을 탐색하는게 아니라,
최소값을 찾아내고, 최소값과 현재 값의 차이로 이익을 탐색하며, 최대 이익을 갱신해나가는 방법이다.
이전 풀이에서 slice()나 스프레드 연산자를 사용하지 않았고, Math.max()도 사용하지 않았기 때문에, 시간을 많이 줄일 수 있었다.

다른 분의 solution

그러나 여전히 필자의 풀이는 성능이 좋지 않았다.
릿코드 기준 50% 이상은 됐지만...말그대로 통과만 된 수준이라고 봐도 무방하다.
이번에는 다른 분의 풀이를 보며 필자의 풀이에서 잘못된 점이 무엇인지 살펴보고자 한다.
아예 공식적으로 고정된 솔루션이 있었다.

two pointer 알고리즘을 사용하신 듯 하다.

const maxProfit = (prices) => {
  let left = 0; // Buy
  let right = 1; // sell
  let max_profit = 0;
  while (right < prices.length) {
    if (prices[left] < prices[right]) {
      let profit = prices[right] - prices[left]; // our current profit

      max_profit = Math.max(max_profit, profit);
    } else {
      left = right;
    }
    right++;
  }
  return max_profit;
};

left는 구매, right는 판매를 담당한다. 이들은 인덱스 값을 의미한다.
또한, max_profit을 0으로 초기화한다.
right가 배열 끝에 닿을 때까지 while문을 반복한다.

만약, 구매 금액(prices[left])이 판매 금액(prices[right])보다 작으면,
이익은 그 차이만큼 발생하며, max_profit과 비교하여 더 큰 값을 max_profit으로 재할당한다.
다음 이익을 계산하기 위해 판매 날짜(right)를 옮겨준다.

만약, 구매 금액(prices[left])이 판매 금액(prices[right])보다 크면,
이는 이익을 낼 수 없는 구조이므로, 구매 날짜(left)를 기존 판매 날짜(right)로 변경한다.
이 때, 같은 날 구매하고 같은 날 판매하면 안되니까 판매 날짜(right) 또한 옮겨준다.

이 방법은 필자가 시간 초과를 해결했을 때 처럼, 불필요한 반복을 사용하지 않았다.
그 것이 중요한 포인트인 것 같다.
로직은 필자와 비슷하기 때문에, 시간 복잡도에서 눈에 띄게 발전하는 것은 없었다.
다만, 필자는 알고리즘적인 사고는 적용하지 않았고, 이 분은 two pointer를 명확하게 사용하셨다.