[LeetCode] 121. Best Time to Buy and Sell Stock

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

Best Time to Buy and Sell Stock - LeetCode

풀이

import collections
from typing import Deque
from typing import List


class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) > 1:
            # 계속 상승하는 그래프일 경우를 위해 0 넣고 시작
            low_point_index = [0]
            profits = []

            # 저점 인덱스 저장
            for i in range(1, len(prices) - 1):
                if (prices[i-1] > prices[i]):
                    low_point_index.append(i)

            # profit 구하기
            for n in low_point_index:
                tmp = max(prices[n+1:]) - prices[n]
                if tmp > 0:
                    profits.append(tmp)

            if len(profits) > 0:
                return max(profits)
            else:
                return 0

        # len(prices)가 0,1인 경우 profit 0
        else:
            return 0


"""
<브루트 포스 - 타임아웃>
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profits = []
        for i in range(len(prices)):
            for j in range(i+1, len(prices)):
                if prices[j] > prices[i]:
                    profits.append(prices[j] - prices[i])
        if len(profits) == 0:
            return 0
        else:
            return max(profits)
"""

브루트 포스 풀이는 타임아웃으로 판정되어서 좀 다르게 풀어봤다.
그래프에서 저점에 해당하는 인덱스를 리스트에 저장했고, 저점에 해당하는 점 뒤로 리스트를 slice하여
구한 max에서 인덱스에 해당하는 price값을 빼주어 profit을 구했다.
실행 속도는 그리 빠르진 않으나 브루트 포스보단 빠르다.
처음에 low_point_index에 0을 넣고 시작한 것은 계속 상승하는 그래프는 price[1:]에서 저점이 없기때문이다.
항상 예외처리를 해 주어 최적화를 해주는것을 잊으면 안된다!(답이 없거나 이런 경우)

"파이썬 알고리즘 인터뷰" 풀이에선 몇배는 더 빠르게 구했다.

더 알아보기

• sys모듈의 maxsize

 

파이썬 알고리즘 인터뷰 국내도서 저자 : 박상길 출판 : 책만 2020.07.15 상세보기