[알고리즘][배열] - 7. 주식을 사고 팔기 가장 좋은 시점

 

📖이 포스팅은 '파이썬 알고리즘 인터뷰 - 박상길님'을 보고 작성되었습니다.

---

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

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

---

[브루트 포스로 계산]

 

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

• 본인이 푼 문제로 맞긴 한데 통과는 못한다. 시간 초과 문제가 일어난다 더 개선해서 풀어보겠다!

 

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        answer = 0
        
        for i, price in enumerate(prices):
            for j in range(i,len(prices)):
                answer = max(prices[j] - price, answer)
        return answer

• 당연 이 풀이도 브루트 포스로 푼 문제라 시간 초과가 뜬다

 

[개인적인 풀이]

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        max_price = 0
        min_price = 0
        for i in range(len(prices)):
            if i == 0:
                min_price = prices[i]
                pass
            min_price = min(min_price, prices[i])
            max_price = max(prices[i] - min_price, max_price)

        return max_price

 

[저점과 현재 값과의 차이 계산]

import sys


class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        max_price = 0
        min_price = sys.maxsize
        for price in prices:
            min_price = min(min_price, price)
            max_price = max(max_price, price - min_price)

        return max_price

• 바로 위 코드와 다른 점은 min_price의 설정 범위의 시작이 달라서 index = 0인 값은 무조건 min_price 처리하고 말고의 문제지만 어쨌든 아래 코드도 젤 큰값을 넣어놨기에 list 안에서 제일 큰 값을 돌려줘도 그 값이 min_price를 주니까 비슷한 풀이긴 하다.
• 실행 시간은 책에 나온 풀이가 더 빠르다