릿코드 121번 문제 Best Time to Buy and Sell Stock 자바스크립트 문제 해석 및 풀이 Leetcode 11 Javascript

오늘은 릿코드 121번 문제인 Best Time to Buy and Sell Stock 자바스크립트 문제 풀이입니다.

Best Time to Buy and Sell Stock

문제설명

이 문제 같은 경우에는 먼저 설명드리자면 1차원 배열이 주어졌을 때에 그 배열의 원소들을 해당 날의 주식으로 봤을 때, 마진을 제일 많이 남길 수 있는 날을 구하는 문제입니다.

예시 1을 살펴보겠습니다.

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.

제일 낮았던 1(2일차, index=1)에 사서 그날 이후 제일 높은 6(5일차, index=4)에 파는 것이 6-1 = 5 로 마진이 제일 많은 것을 확인 할 수 있습니다. 리턴값은 날짜가 아닌 profit입니다.

 

예시 1과 다르게 프로핏(마진)을 남기지 못할 경우, 0을 리턴해줍니다.

 

문제풀이

For loop 하나 이용

루프 하나를 이용해서 min값을 할당해가며 profit을 계산 먼저 계산해 준 후 만약 현재 인덱스 시점에서 maxPofit이 profit보다 크다면 maxProfit을 업데이트 해줍니다.

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

루프 안 코드는 아래 코드로 대체됩니다.

        min = Math.min(min, prices[i]);
        profit = prices[i] - min;
        maxProfit = Math.max(profit, maxProfit);

 

코드를 보면서 이해하시면 될 듯 합니다.

For loop 하나 이용 성능

Best Time to Buy and Sell Stock performance

1. 시간복잡도는 인자로 들어온 prices 배열의 갯수만큼 루프가 돌았으니 O(n)이 됩니다.
2. 공간복잡도는 별도의 공간을 생성해주지 않았기 때문에 O(1)이 됩니다.

---

이상으로 릿코드 121번 문제 Best Time to Buy and Sell Stock을 풀어보았습니다.

 

121. Best Time to Buy and Sell Stock

 

 

Easy

 

 

22.7K

 

718

 

 

Companies

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.

 

Example 1:

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.

Example 2:

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

 

Constraints:

• 1 <= prices.length <= 105
• 0 <= prices[i] <= 104

 

※ 앞으로 모든 문제를 JavaScript 로 올릴 예정입니다.

릿코드 연습을 하며 올린 포스팅이므로 간혹 틀린 부분이 있을 수 있습니다.

혹시 잘못된 부분이 있을 경우 댓글 남겨주시면 감사드리겠습니다.

다른 문제 풀이도 깃헙에서 확인 할 수 있습니다.