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

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

---

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

 

문제 정의

한 번의 거래로 낼 수 있는 최대 이익을 산출하라

 

책에서 구현된 코드

def maxProfit(self, prices: list[int]) -> int:
    profit = 0
    min_price = sys.maxsize
    
    for price in prices:
        min_price = min(min_price, price)
        profit = max(profit, price - min_price)
        
    return profit

 

기억해야할 기법

• 최소값을 최대값으로 지정
  
  • sys.maxsize
• 더 작은 값, 더 큰 값으로 업데이트할 경우
  • if문이 아닌 min / max를 활용하여 가독성을 높일 것
• min_price가 현재값(price)보다 무조건 작거나 같음이 보장되므로, 음수에 대한 처리를 할 필요가 없음

 

내가 구현한 코드

def update(x, y, profit):
    if x < y and y - x > profit:
        return y - x
    return profit

def best_stock(prices: list[int]) -> int:
    if len(prices) < 1:
        return 0

    min_num = prices[0]
    profit = 0

    for i in range(1, len(prices)):
        crnt = prices[i]
        nw_profit = update(min_num, crnt, profit)

        if profit < nw_profit:
            profit = nw_profit

        if crnt < min_num:
            min_num = crnt

    return profit

• 속도에서 약간 차이가 나는 이유를 알아봐야할 것
• 가독성의 차이가 매우 크다
• 내가 구현한 알고리즘

• 책에서 구현한 알고리즘