[LeetCode/JS] 121. Best Time to Buy and Sell Stock - 2가지 풀이 방법

문제 링크

• https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

문제 설명

1. 주가(stock)로 이뤄진 배열이 주어지고 해당 인덱스은 일자를 나타낸다.
   ex) prices[i] -> i번째날
2. 주어진 주가에서 구매와 판매를 각 한번씩 할 수 있다고 가정했을 때 최대 수익률은 얼마인지 반환하라

주제

• Array

난이도

• Easy

1차 풀이 - Brute Force

/**
 * @param {number[]} prices
 * @return {number}
 */
const maxProfit = function(prices) {
    let profit = 0;
    
    for(let i=0; i<prices.length; i++) {
        for(let j=i+1; j<prices.length; j++) {
            if (prices[i] > prices[j]) {
                continue;
            }
            profit = Math.max(profit, prices[j] - prices[i])
        }
    }
    
    return profit
    
};

풀이 방법

1. 중첩 루프를 이용하여 각 인덱스끼리 더한 값 중 제일 큰 값을 반환한다.

시간 복잡도 - Time Limit Exceeded (머쓲,,)

• O(n2)
  
  

2차 풀이

/**
 * @param {number[]} prices
 * @return {number}
 */
const maxProfit = function(prices) {
    let profit = 0;
    let min = prices[0]
    
    for (let i=1; i<prices.length; i++) {
        min = Math.min(min, prices[i-1])    // 구매 금액은 항상 판매 금액보다 앞인덱스에 있어야 하므로 i-1를 해준다.
        profit = Math.max(prices[i]-min, profit)
    }
    
    return profit
};

풀이 방법

1. 구매와 판매 금액을 한번씩 비교해가며 값을 찾아낸다.

시간 복잡도

• O(n)

문제를 풀고 알게된 개념 및 소감

왜 나는 값을 비교하라고하면 중첩반복문부터 생각이 나는 걸까..
아무래도 가장 단순하면서도 빠르게 구현할 수 있기 때문이겠지.

중첩반복문을 생각한게 잘못된건 아니다. 하지만 중첩반복문만이 답이라고 생각하는건 잘못된거다.

충분히 로직만 잘 생각하면 훨씬 효율적으로 할 수 있는 방법들은 언제나 존재한다.

좀 더 넓은 시야를 갖자..