본문 바로가기

Leetcode

[Leetcode] 122. Best Time to Buy and Sell Stock II - JS

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/description/?envType=study-plan-v2&envId=top-interview-150

 

1. 문제 분석

문제분석
--------------------
- 정수배열 prices, prices[i]는 i번째 날짜의 주가이다.
- 매일 주식을 사거나 팔 수 있다.
- 주식은 최대 1개만 가질 수 있다.
- 그날 사서 같은 날에 팔 수도 있다.
- 최대 이익을 반환하라.

제한조건
--------------------
- 1 <= prices.length <= 3 * 10^4
- 0 <= prices[i] <= 10^4

 

 

2. 접근 방법

접근방법
--------------------
이전 문제와 달리 한번만 사고 파는 것이 아닌 여러번 사고 팔수 있다.
즉, profit이 누적될 수 있다는 뜻이다.

 

 

3. 코드

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

- 이익이 생겼을 때만 이익에 누적하여 최대 이익을 구한다.

 

내가 머릿 속으로 유념했던 부분은 [7, 1, 5, 1, 7, 9, 6] 으로 주어졌을 때,

최대 이익은 (5 - 1) + (9 - 1) = 12 인데, 위 로직대로는 (5 - 1) + (7 - 1) + (9 - 7) = 12 로 계산되는 것이었다.

두 방법 모두 동일한 최대 이익을 구하는데 그렇지 않은 예외 케이스가 있을지 생각해보게되었다.

 

4. 복잡도 분석

- 시간복잡도: O(n)

- 공간복잡도: O(1)