문제
https://leetcode.com/problems/best-time-to-buy-and-sell-stock/?envType=study-plan-v2&envId=top-interview-150
더보기
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
✔ 문제접근 #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):
# index 0 ~ i - 1까지 값들 중 가장 작은 값과 비교한다.
ans = max(ans, prices[i] - min_val)
# 지금까지 들어온 값들 중 가장 작은 값을 갱신한다.
min_val = min(min_val, prices[i])
return ans
Complexity Analysis
- 시간 복잡도 : O(N)
- 배열을 순차탐색 O(N)
- 공간복잡도 : O(1)
기타풀이 및 회고
배열을 순회하며 지금까지 순회해온 내용들중 최소, 혹은 최대값을 갱신해주는 아이디어가 포인트이다. 마치 다이나믹 프로그래밍에서 시작부터현재위치값까지의 최댓값 혹은 최솟값을 기록해주는 방식과 똑같다. 만약 이런식으로 최대, 최솟값을 갱신해오지 않았다면 완전탐색을 통해서 살 위치와, 팔 위치를 골라야 하기 때문에 시간복잡도 O(N**2)이 나왔을 것이다.
'algorithm > 리트코드' 카테고리의 다른 글
[리트코드] 55. Jump Game (0) | 2023.09.01 |
---|---|
[리트코드] 122. Best Time to Buy and Sell Stock II (0) | 2023.09.01 |
[리트코드] 189. Rotate Array (0) | 2023.09.01 |
[리트코드] 242. Valid Anagram (0) | 2023.09.01 |
[리트코드] 383. Ransom Note (0) | 2023.09.01 |