LeetCode [121]: Best Time to Buy and Sell Stock

📌 LeetCode [121]: Best Time to Buy and Sell Stock

🔗 문제 링크

---

문제 설명 📄

주어진 주식 가격 배열 prices에서 주식을 한 번 사고 한 번 팔았을 때 얻을 수 있는 최대 이익을 계산하는 문제입니다.

• 주식은 미래의 가격을 알 수 없으므로 한 번만 사고, 한 번만 팔 수 있습니다.
• 주식은 반드시 산 이후에 팔아야 합니다.

---

문제 접근 방식 📋

1. 최소 가격과 최대 가격 관리:
   • 배열을 순회하며 최소 가격(minIndex)과 최대 가격(maxIndex)를 갱신합니다.
   • 최소 가격 이후에 최대 가격이 나타나는 경우만 이익을 계산합니다.
2. 효율성:
   • 배열을 한 번 순회하며 최대 이익을 계산하므로, 시간 복잡도는 O(n)입니다.

---

Solution 💻

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        minIndex = 0
        maxIndex = 0
        answer = 0

        for i in range(1, len(prices)):
            # 최소 가격 이후에 최대 가격일 때 이익 계산
            if minIndex < maxIndex:
                answer = max(answer, prices[maxIndex] - prices[minIndex])
            else:
                maxIndex = minIndex

            # 최소 가격 및 최대 가격 갱신
            if prices[minIndex] > prices[i]:
                minIndex = i
            if prices[maxIndex] < prices[i]:
                maxIndex = i

        # 마지막으로 최소 가격 이후에 최대 가격일 경우 이익 계산
        if minIndex < maxIndex:
            answer = max(answer, prices[maxIndex] - prices[minIndex])

        return answer

시간 복잡도 분석 ⏲️

• 시간 복잡도: O(n)
  • 배열을 한 번 순회하며 최소/최대 가격 및 최대 이익을 갱신합니다.
• 공간 복잡도: O(1)
  • 추가 메모리를 사용하지 않습니다.

---

리팩토링 🛠️

개선된 코드

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # 최소 가격 초기화
        min_price = float('inf')
        max_profit = 0

        for price in prices:
            # 최소 가격 갱신
            min_price = min(min_price, price)
            # 최대 이익 갱신
            max_profit = max(max_profit, price - min_price)

        return max_profit

---

리팩토링 코드의 차이점

1. 불필요한 인덱스 제거:
   • minIndex와 maxIndex 대신 현재 최소 가격(min_price)만 관리하여 코드 간결화.
2. 최대 이익 계산 간소화:
   • price - min_price를 즉시 계산하여 최대 이익(max_profit)을 갱신.

시간 복잡도 분석 ⏲️

• 시간 복잡도: O(n)
  • 배열을 한 번 순회.
• 공간 복잡도: O(1)
  • 추가 메모리 사용 없음.

---