[LeetCode_121] 주식을 사고팔기 가장 좋은 시점

파이썬으로 배우는 알고리즘 책을 공부하며 풀었던 LeetCode문제들을 재정리해보자.

 

# 문제 설명 

121번 Product of Array Except Self은 주어진 주식 가격 배열에서 한 번의 거래로 낼 수 있는 최대 이익을 계산해내는 문제이다.

만약 이익이 없다면, 0을 return 하면 된다.

 

 

# 풀이방법 1 - 뒤에서부터 고점 계산 후 이익 계산 (내 풀이 - 비효율적)

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        
        
        maxPrice = -1 
        maxProfit = 0

        # 오른쪽 부터 접근하여, 가장 가격이 비싼 값(고점)과 이익이 가장 큰 값을 계산함
        for i in range(len(prices)-1, 0, -1) : 

            if prices[i] > maxPrice :
                maxPrice = prices[i]

            if (maxPrice - prices[i-1]) > maxProfit :
                maxProfit = maxPrice - prices[i-1]

        return maxProfit

아이디어 : 오른쪽부터 접근하여 누적으로 가장 가격이 비싼 값(고점)을 저장하고, 이익이 가장 큰 값을 계산한다.

 

 

# 풀이 방법 2 - 앞에서부터 저점과 현재 값과의 차이 계산 (책 풀이 참고)

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        
        
        min_price = sys.maxsize 
        profit = 0

        for price in prices :
            min_price = min(min_price, price)
            profit = max(profit, price-min_price)
            
        return profit

내가 푼 방식과 달리 최저점을 저장하며 이익을 계산함

 

 

 

 

 

# 결과 

저 Time Limit Exceeded는 첫 시도를 브루트포스로 풀어서 생김,,ㅎㅎ