LeetCode 풀기 - 121. Best Time to Buy and Sell Stock

알고리즘/LeetCode

LeetCode 풀기 - 121. Best Time to Buy and Sell Stock

앤테바 2022. 2. 25. 05:07

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

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

문제)

솔루션1) Bruete-Force

Brute-force 방식으로 풀면 시간 초과가 발생하네요.

시간 복잡도 : O(n^2)

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

솔루션2) max price 계산

솔루션1은 O(n^2)이기 때문에 시간 초과가 발생합니다.

이를 줄여합니다.

현재 산 가격에서 가격이 최대인 날을 배열의 끝까지 찾는데, 이를 줄이는 방법이 필요합니다.

가격이 최대인 날을 미리 계산 해 놓은면 어떨까???

가격:

prices = [7, 1, 5, 3, 6, 4]

가격이 최대:

max_prices = [7, 6, 6, 6, 6, 4]

그렇다면 max_prices[i] - prices[i] 빼면 i day에 최대 수익을 찾을 수 있네요

시간 복잡도 : O(2n)

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # 가격을 뒤에서 부터 max 값 찾기
        # ex) [7, 6, 6, 6, 6, 4]
        max_prices = prices[::-1]
        for i in range(1, len(max_prices)):
            max_prices[i] = max(max_prices[i-1], max_prices[i])            
        max_prices.reverse()
        
        # 최대 이익을 계산
        max_profit = 0
        for a, b in zip(prices, max_prices):
            max_profit = max(max_profit, b-a)
        return max_profit

솔루션3) left, right index

discuss에서 솔루션을 살펴보니 더 직관적이고 빠르게 푸는 방법이 있네요.

left, right 두 인덱스를 유지하고 left 인덱스에서는 사고, right 인덱스에서는 파는 것입니다.

left, rigt 인덱스는 price에 따라서 위치를 이동 시킵니다.

Buy	Sell	profit
7	1	-6
1	5	4
1	3	2
1	6	5
1	4	3

시간복잡도 : O(n)

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # buy index
        left = 0
        # sell index
        right = 1
        
        max_profit = 0
        while right < len(prices):
            max_profit = max(max_profit, prices[right] - prices[left])

            if prices[left] < prices[right]:
                right += 1
            else:
                left = right
                right = left + 1
        return max_profit

솔루션4) Kadane's Algorithm

카데인 알고리즘을 활용한 풀이 기법입니다.

시간복잡도 : O(n)

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # Kadane's Algorithm
        
        max_profit = 0
        cur_sum = 0
        for i in range(len(prices)-1):
            cur_sum += prices[i+1] - prices[i]
            if cur_sum < 0:
                cur_sum = 0
            max_profit = max(max_profit, cur_sum)
        return max_profit