문제
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/?envType=study-plan-v2&envId=top-interview-150
더보기
Example 1:
Input: prices = [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Total profit is 4 + 3 = 7.
Example 2:
Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Total profit is 4.
Example 3:
Input: prices = [7,6,4,3,1]
Output: 0
Explanation: There is no way to make a positive profit, so we never buy the stock to achieve the maximum profit of 0.
Constraints:
- 1 <= prices.length <= 3 * 10**4
- 0 <= prices[i] <= 10**4
✔ 문제접근 #1 그리디[통과] ⭕
Intuition
가장 낮은 지점일 때 사고, 가장 높은 지점(고점)에서 팔아버린다. 가격이 떨어진다면 그자리에서 사서 그자리에서 팔아버린다. 다음 과정을 반복하며 전체 가격을 순회한다.
Algorithm
전체 가격을 순회하며 바로 직전 가격보다 현재 가격이 더 높다면 계속 상승중이므로 그냥 넘어간다.
만약 이전가격보다 현재가격이 작아진다면 상승세가 멈추었기 때문에 현재가격에서 사버리고 최솟값이 현재가격이므로 다시 팔아버린다.
맨 마지막값일 때 상승중일 수 있기 때문에 팔아준다. 만약 하락중이었다고 하더라도 최솟값은 자신이 될 것이기 때문에 영향을 미치지 않는다.
def maxProfit(self, prices: List[int]) -> int:
# 값이 오르다가 최대점이 찍힐 때 판다?
n = len(prices)
min_val = prices[0]
ans = 0
for i in range(1, n):
# 계속 상승중이라면 넘어간다.
if prices[i - 1] < prices[i]:
continue
# 상승세가 끊긴다면 i - 1부분이 최대치이다.
if prices[i - 1] > prices[i]:
ans += prices[i - 1] - min_val
min_val = prices[i]
ans += prices[n - 1] - min_val
return ans
Complexity Analysis
- 시간 복잡도 : O(N)
- prices 배열을 순차탐색 O(N)
- 공간복잡도 : O(1)
기타풀이 및 회고
이 문제는 파는곳이 1곳이 정답일 수 도있고, 여러곳에서 파는것이 정답일 수 도 있다. 그렇기 때문에 언제 팔아야 최대값을 낼 수 있는지를 생각해 내는 것이 관건다. 그리디 방법이라고 생각할 수 있는데, 바로 계속해서 가격이 상승하다가 최대치를 찍는 순간 파는 것이 가장 이득이라고 생각할 수 있다.
'algorithm > 리트코드' 카테고리의 다른 글
[리트코드] 162. Find Peak Element (0) | 2023.09.05 |
---|---|
[리트코드] 55. Jump Game (0) | 2023.09.01 |
[리트코드] 121. Best Time to Buy and Sell Stock (0) | 2023.09.01 |
[리트코드] 189. Rotate Array (0) | 2023.09.01 |
[리트코드] 242. Valid Anagram (0) | 2023.09.01 |