Leetcode - Best Time to Buy and Sell Stock

23 Oct 2024 in Algorithm

알고리즘 공부

Daily Leetcode

• 🔨 Naive Solution
• 🔮 Best Solution

문제 링크

문제는 해석하면 가장 수익을 많이 낼 수 있도록 저점에 매수, 고점에 매도 후 얻는 수익을 리턴하는 것이다.

🔨 Naive Solution

딱 떠오르는 아이디어는 포인터를 이용해 모든 날의 가격을 조회하면서 가장 저점이었던 날을 빼 나가는 것이다. 코드로 보자

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
    """
    가장 수익을 많이 얻을 수 있도록 저점에 매수, 고점에 매도

    매수와 매도는 서로 다른 날
 
    """

    min_price = max(prices)
    days = len(prices)
    dp = [min_price for _ in range(days)]

    for day in range(days):
        if prices[day] < min_price:
            min_price = prices[day]
        dp[day] = prices[day] - min_price

    return max(dp)

• TC : O(N)

• SC : O(N)

dp 리스트를 쓰면서 가장 수익을 많이 낼 수 있도록 구하고 있다. 이때 공간복잡도를 개선할 수 있을까?

🔮 Best Solution

위 코드를 보다보면 굳이 dp 리스트가 필요없어 보인다. 그 이유는 한 번 본 prices는 더 이상 쓰이지 않기 때문이다.

코드를 아래와 같이 짜보자.

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        """
        가장 수익을 많이 얻을 수 있도록 저점에 매수, 고점에 매도
    
        매수와 매도는 서로 다른 날
    
        """

        min_price = max(prices)
        days = len(prices)
    
        for day in range(days):
            if prices[day] < min_price:
                min_price = prices[day]
            prices[day] -= min_price
    
        return max(prices)

• TC : O(N)

• SC : O(1)

Easy 난이도였으며 굉장히 빨리 풀 수 있었다. 아래는 그 결과이다.