[LeetCode#122] Best Time to Buy and Sell II

 

❒ Description

---

날짜	2024.09.16 (월)
제목	Best Time to Buy ans Sell II
링크	https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/description/
자료구조	배열 & 스택
알고리즘	그리디
시간 복잡도	O(n)

 

이번 문제는 배열 또는 스택을 사용하여 풀이할 수 있는 문제이다.

물론 스택을 사용하면 메모리를 더 사용한다는 단점은 존재한다.

그리고 이 문제는 [LeetCode#739] Daily Temperature 풀이에서 아이디어 하나만 추가하면 된다. 

 

 

 

 

 

❒ Solution

---

1. Stack

public int maxProfit(int[] prices) {
    Deque<Integer> stack = new ArrayDeque<>();
    int[] result = new int[prices.length];
    for (int i = 0; i < prices.length; i++) {
        while (!stack.isEmpty() && prices[i] > prices[stack.peek()]) {
            int index = stack.pop();
            result[index] = prices[i] - prices[index];
            stack.clear(); // ← 추가 된 부분
        }
        stack.push(i);
    }
    return Arrays.stream(result).sum();
}

[LeetCode#739] Daily Temperature 풀이와 차이는 stack.clear(); 이 부분이다.

이 문제는 모든 인덱스에서 얼마의 이윤을 냈는지가 아니라 저점일 때 사고 고점일 때 파는 문제이기 때문이다.

따라서 `[1, 2 , 3]` 이런 경우에는 1에서 사서 3에서 팔기 때문에 1과 3만 신경쓰고 2는 신경쓰지 않아도 된다.

 

 

 

2. Array

public int maxProfit(int[] prices) {
    int maxProfit = 0;
    for (int i = 1; i < prices.length; i++) {
        int dailyProfit = prices[i] - prices[i - 1];
        if (dailyProfit > 0) {
            maxProfit += dailyProfit;
        }
    }
    return maxProfit;
}

스택을 사용한 풀이와 시간 복잡도는 O(n)으로 동일하지만, 배열 자료구조만 사용하였기 때문에 메모리 사용

측면에서 보다 효율적인 코드라고 할 수 있다.

 

 

 

 

 

---