Best Time to Buy and Sell Stock II

Best Time to Buy and Sell Stock II

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/

문제 요약

• 주식 가격이 담긴 prices 배열이 주어진다.
• 각각의 날마다 사거나 팔 수 있다. 하지만 1개 이하의 주식만 가질 수 있다. (동시에 여러개를 매도할 수 없다)
• 그리고 같은 날에 사서 팔수도 있다.
• 최대 이익을 return

풀이

• prices 배열의 최대 길이는 30_000으로 O(n), O(nlogn) 풀이가 가능하다.
• 판매한 당일에도 주식 구매가 가능함
• 그리디 유형의 문제이므로 현재 할 수 있는 최선의 선택을 해야 함
  • 가격이 올랐을 때 주식을 사고 가격이 떨어졌을 때 주식을 판매
• prices 배열을 인덱스 1부터 끝까지 돌면서 현재를 판매 기준으로 보고 이익을 계산

예시

prices = [3, 2, 1, 4]

1. buy 3 -> sell 2 이익이 없으므로 패스
2. buy 2 -> sell 1 이익이 없으므로 패스
3. buy 1 -> sell 4 이익 = 4 - 1 = 3

prices = [7, 1, 5, 3, 6, 4]

1. buy 7 -> sell 1 X
2. buy 1 -> sell 5 O(5 - 1 = 4)
3. buy 5 -> sell 3 X
4. buy 3 -> sell 6 O(6 - 3 = 3)
5. buy 6 -> sell 4 X

prices = [1, 3, 0, 1, 3, 0]

수도 코드

def sol(prices):
	answer = 0
    
    for i = 1...prices.len:
    	이익 = 판매 가격[i] - 구매 가격[i - 1]
        if 이익 > 0:
        	answer += 이익
            
    return answer

Solution(Runtime: 65ms)

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        answer = 0

        for i in range(1, len(prices)):
            profit = prices[i] - prices[i - 1]
            answer += profit if profit > 0 else 0

        return answer

그리디 유형의 문제였다. 즉, 현재 가장 최선의 방법을 택해야 한다. 따라서 싸게 구매해서 다음날 이익이 나면 판매하는 방식으로 구현하였다.