121. Best Time to Buy and Sell Stock ☆

121. Best Time to Buy and Sell Stock

 

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # 먼저 사고 팔수 있음
        bestProfit = 0
        lp = len(prices)
        for buy_i in range(lp-1):
            for sell_i in range(buy_i+1, lp):
                profit = prices[sell_i]-prices[buy_i]
                bestProfit = max(bestProfit, profit)
        return bestProfit

 

Time Limit Exceeded

지금 코드도 문제를 맞게 풀긴 하지만, **시간복잡도는 O(n²)**입니다.

입력이 커지면 **Time Limit Exceeded (TLE)**가 발생할 수 있어요.

 

✅ 더 빠른 O(n) 최적화 풀이

한 번의 순회로 최소값을 갱신해가며 최대 이익을 계산할 수 있습니다.

 

🔍 핵심 아이디어

• 매일 주가를 볼 때, 그날을 팔 날로 생각하고,
• 지금까지 본 **가장 싼 날(살 날)**과의 차이를 계산해보면,
• 결국 한 번의 루프로 최대 이익을 구할 수 있어요.

예시

prices = [7, 1, 5, 3, 6, 4]
최대 이익: 5 (1일에 사서, 4일에 팜)

 

최종 코드

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # 먼저 사고 팔수 있음
        # O(N) 으로!!

        maxProfit = 0  # 현재까지의 최대 이익
        minBuy = float("inf")  # 지금까지의 최소 구매가

        for price in prices:
            # 매번, 최소 구매가격 갱신
            minBuy = min(minBuy, price)  # 가장 싸게 살 수 있는 날 갱신

            # 매번, 최대 이익 갱신
            # 항상 최소 구매 가격 갱신 후, 최대 이익 계산이 이루어지기 때문에,
            maxProfit = max(maxProfit, price-minBuy)  # 오늘 팔면 얼마 남는지 계산해서 최대 이익 갱신
        return maxProfit

 

정리하자면:

• 시간복잡도: O(N)
• 공간복잡도: O(1)