[알고리즘] Leetcode #122 주식을 사고팔기 가장 좋은 시점 2 (Python)

---

↓↓↓ 아래는 내 리트코드 계정 ↓↓↓

leetcode.com/Jiwon_Lee/

Jiwon Lee - LeetCode Profile

 

---

문제 설명

You are given an array prices where prices[i] is the price of a given stock on the ith day.

Find the maximum profit you can achieve. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

 

입출력 예

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.

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. Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again.

Example 3:

Input: prices = [7,6,4,3,1] Output: 0 Explanation: In this case, no transaction is done, i.e., max profit = 0.

 

Constraints

• 1 <= prices.length <= 3 * 104
• 0 <= prices[i] <= 104

 

Code

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

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

이 문제는 배열에서 최저점에 샀다가 최고점에 파는 문제와 유사하지만, 여러 번 거래할 수 있다는 점에서 차이가 있다. 그리디를 적용할 수 있는 문제로, 주가가 오르기 전에 사서 내리기 전에 파는 전략으로 생각할 수 있다. 따라서, result에는 가격이 오를 때마다 팔아서 얻는 이익을 할당한다. 또는, 파이썬의 특징을 활용해 코드를 간단히 할 수 있다. 두 번째 코드와 같이, i+1 시점의 가격에서 i시점의 가격을 뺀 금액이 0보다 클 경우, 그 차이를 모두 합산해주는 방식이다. 이렇게 되면 매 거래마다 이익을 보면서 거래를 반복할 수 있다.

---

 

 

I'm a Senior Student in Data Science ! 

데이터 사이언스를 공부하고 있는 학부생의 TIL 블로그입니다. 게시글이 도움 되셨다면 구독과 좋아요 :)