[LEETCODE 150] - 121 Best Time to Buy and Sell Stock II

LeetCode의 122번 문제인  "Best Time to Buy and Sell Stock II" 문제이다

 

이 문제도 이전 121번문제와 비슷하게 그리디 알고리즘을 통해서 푸는 방식이다.

알고리즘을 풀면서 가장 중요한게 " 가격이 오르는 구간의 이익을 전부 더하면, 여러번 사고 팔아 얻을수 있는 최대 이익과 같아진다" 라는 개념을 알고있어야 한다.

 

정답 코드(Python)

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

 

풀이 해석

• profit : 지금까지 벌어들인 총 이익을 저장(초기 0원)
• i를 1부터 끝까지 돌림(prices[i - 1]'전날가격'과 비교하려면 i = 0은 불가능)

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit = 0
        
        for i in range(1, len(prices)):

• 오늘 가격이 어제보다 올랐다면
  • 그 상승분만큼 이익을 profit에 더함
• 즉 "어제사서 오늘 팔았다"고 가정하고 모든 상승분을 전부 챙기는 방식
• 모든 날을 확인한 뒤 누적된 최대 이익 반환

if prices[i] > prices[i - 1]:
	profit += (prices[i] - prices[i - 1])
    
    return profit

 

왜이게 최대 이익이 되나??

예를들어 가격이 이렇게 움직이면

[1,2,3,4]

• 상승분 합: (2-1) + (3-2) + (4-3) = 1 + 1 + 1 = 3
• 실제로 "1에 사서 4에 팔기" 이익도 3이라서 같음.
• 한번에 길게 가져가든 중간에 여러번 사고팔든 결과 이익은 상승 구간의 '총 상승량'과 동일하다.