몰입공간
[Leetcode] 122. Best Time to Buy and Sell Stock II (python) 본문
Algorithm/Leetcode
[Leetcode] 122. Best Time to Buy and Sell Stock II (python)
sahayana 2023. 8. 24. 21:42#1. 문제
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii
Best Time to Buy and Sell Stock II - LeetCode
Can you solve this real interview question? Best Time to Buy and Sell Stock II - You are given an integer array prices where prices[i] is the price of a given stock on the ith day. On each day, you may decide to buy and/or sell the stock. You can only hold
leetcode.com
121번 문제의 심화 버전이다.
하루에 보유할 수 있는 최대 주식의 갯수가 1개일 때, 다수의 거래로 발생 가능한 최대 이익을 찾는 문제다.
# input
prices = [3,3,5,0,0,3,1,4]
# output
Output: 8
# explanation
idx = 1 가격 3에 구매하여 idx = 2 가격 5에 팔면 수익이 2
idx = 4 가격 0에 구매하여 idx = 5 가격 3에 팔면 수익이 3
idx = 6 가격 1에 구매하여 idx = 7 가격 4에 팔면 수익이 3
총 이익: 8
#2. 풀이
class Solution:
def maxProfit(self, prices: List[int]) -> int:
import collections
prices = collections.deque(prices)
profit = 0
buy = prices.popleft()
while prices:
sell = prices.popleft()
if sell > buy:
profit += (sell - buy)
buy = sell
return profit
예시에 나오는 해설로 인해 쉽게 호도될 수 있는 문제다.
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.
당장 최적해를 얻을 수 있는 방법(그리디)로 문제를 풀면 쉽게 해결할 수 있다.
한번에 보유 가능한 주식(1개)만 지킨다면 전체 day의 다수의 거래도 상관없기 때문에 이익을 낼 때마다 더해준다.

시간을 정말 많이 투자한 문제다.
투포인터, 비교, 해시맵등등 아무리 최적화를 하려고 해도 계속 O(N*3)의 시간복잡도가 나왔다.
완성한 알고리즘은 예시를 다 통과해도 정작 몇개의 특수 케이스를 통과하지 못했다.
이것만 해결하면 될 거라는 생각에 매몰되어 시간가는 줄 모르고 계속 시도했지만 쉽지 않았다.
문제를 다시 복기하면서 결국 문제 요구사항을 잘 못 이해하고 있다는 것을 깨달았다.
'Algorithm > Leetcode' 카테고리의 다른 글
[Leetcode] 125. Valid Palindrome (python) (0) | 2023.08.26 |
---|---|
[Leetcode] 55. Jump Game (python) (0) | 2023.08.25 |
[Leetcode] 121. Best Time to Buy and Sell Stock (python) (0) | 2023.08.24 |
[Leetcode] 169. Majority Element (python) (0) | 2023.08.23 |
[Leetcode] 80. Remove Duplicates from Sorted Array II (python) (0) | 2023.08.23 |
Comments