[그리디 알고리즘] 주식을 사고팔기 가장 좋은 시점Ⅱ

122 | Best Time to Buy and Sell Stock II
https://leetcode.com/problems/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 at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.

Find and return the maximum profit you can achieve.

 

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 * 104
• 0 <= prices[i] <= 104

 

작성 코드

 

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        answer = 0
        for idx, price in enumerate(prices):
            answer += max(prices[idx : ]) - price
            print(max(prices[idx : ]) - price)
        print(answer)
        return answer

 

• 실패 ! 
• 현재 요소의 위치부터 슬라이싱 한 배열에서 가장 큰 값을 구함, 구한 값에서 현재 요소를 빼면 현재 요소 이후 가장 차이가 큰 값을 구할 수 있었음
• 그러나 주식을 한 번에 최대 한 가지밖에 소유하지 못하기 때문에 틀린 풀이

 

 

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        answer = 0
        for idx in range(1, len(prices)):
            if prices[idx] - prices[idx - 1] > 0:
                answer += prices[idx] - prices[idx - 1]
        return answer

 

• 첫 번째 인덱스부터 돌도록 함
• '현재 인덱스 값'에서 '현재 인덱스 - 1 한 값'을 뺀 것이 0 보다 크다면, 즉 바로 이전의 값이 더 작다면 판다!
• 1 - 3 - 5 라면 1 - 5 로 한 번에 가는 것이 이상적이지만, 그냥 1 - 3, 3 - 5 따로 간다! 어차피 여러 번 더해도 되니까!

 

 

참고 코드

 

그리디 알고리즘

 

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        result = 0
        # 값이 오르는 경우 매 번 그리디 계산
        for i in range(len(prices) - 1):
            if prices[i + 1] > prices[i]:
                result += prices[i + 1] - prices[i]
        return

 

• 직접 푼 풀이랑 매우 유사!
• 차이점은 직접 풀었을 때는 1 ~ 마지막 인덱스라면 책에서는 0 ~ 마지막인덱스 - 1 까지 반복문을 돔

 

 

파이썬다운 방식

 

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # 0보다 크면 무조건 합산
        return sum(max(prices[i + 1] - prices[i], 0) for i in range(len(prices) - 1))

 

• 마찬가지로 그리디 알고리즘임
• max(prices[i + 1] - prices[i], 0) 이 코드 부분이 포인트 -> 만약 이후에 오르지 않더라도 max 를 통해 0을 더하기 때문에 결과 값에 지장도 없을뿐더러 조건문도 필요 없음!

 

 

회고

 

• 그리디는 생각을 너무 많이 하면 오히려 복잡해지는 듯
• 정답이랑 유사하게 풀어서 뿌듯