[파이썬 알고리즘 인터뷰][그리디] 주식을 사고팔기 가장 좋은 시점2

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 

---

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

 

문제 정의

주식 가격이 시간순으로 주어질 때 최대 이익 출력

 

책에서 구현된 코드

from typing import List


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))

 

기억해야할 기법

• "그리디 알고리즘으로 접근해야한다"는 힌트를 어디서 얻을 수 있을까
  
  • 문제를 잘 해석하면 모든 이익의 합산이다
  • sell & buy를 동시에 할 수 있다는 것을 캐치하면 쉬운 문제였다
  • 나는 나중에 팔았을 때 더 이득을 보는 경우가 있는지 계산을 해본 후에 코드를 작성할 수 있었다
  • 비슷한 문제를 많이 풀어서 감을 찾아야겠다

 

내가 구현한 코드

from typing import List

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

• max로 구현하는 게 더 짧아서 보기 좋은 것 같다