2. Best Time to Buy and Sell Stock

📈 [Python] Best Time to Buy and Sell Stock — 최대 이익 문제 풀이 (LeetCode Easy)

 

Problem: You are given an array prices where prices[i] is the price of a given stock on the i-th day. You must choose a day to buy and a future day to sell to maximize your profit.

 

---

 

🧠 문제 설명 (Problem Description)

 

정수 배열 prices가 주어질 때, 한 번의 **매수(buy)**와 **매도(sell)**를 통해 낼 수 있는 **최대 이익(max profit)**을 구하라.

 

단, 매수는 **매도 이전(day i < j)**에 일어나야 한다.

 

 

💡 예시 입력 / 예시 출력 (Examples)

Input: prices = [7, 1, 5, 3, 6, 4]
Output: 5  # 1에 사서 6에 팔면 5 이익

Input: prices = [7, 6, 4, 3, 1]
Output: 0  # 이익 낼 수 없음

 

---

 

❌ 첫 번째 시도 (My Wrong Attempt)

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        min_prices = 10
        max_profit = 0
        for price in prices:
            if price < min_prices:
                min_prices = price
            elif price - min_price > max_profit:
                max_profit = price - min_price
            return max_profit

 

🧨 문제점 (What went wrong?)

 

1. min_prices vs min_price → 변수 오타 (Variable typo)
2. return이 for문 안에 있어서 반복문이 한 번에 끝남 (Premature return inside loop)
3. 최소값 초기화를 10으로 함 → 작은 가격이 오면 잘못된 결과 유발 가능

 

---

 

✅ 정답 풀이 (Correct Solution)

from typing import List

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        min_price = float('inf')  # 현재까지의 최소 주가 (Set minimum price to infinity)
        max_profit = 0            # 최대 이익 (Maximum profit)

        for price in prices:
            if price < min_price:
                min_price = price  # 더 낮은 가격 발견 → 갱신 (Update minimum if lower price found)
            elif price - min_price > max_profit:
                max_profit = price - min_price  # 더 큰 이익 발견 → 갱신 (Update profit if better deal)

        return max_profit

 

---

 

🔍 핵심 로직 요약 (Logic Summary)

개념 (Concept)설명 (Explanation)

min_price	지금까지 나온 가장 낮은 주가
price - min_price	현재 시점에서 팔았을 때 이익
max_profit	가능한 이익 중 최대값을 저장

이 문제는 **Greedy Algorithm (탐욕법)**의 대표적인 예로,

각 날마다 “지금 팔면 얼마 벌 수 있을까?”를 계산해서 그중 최고 이익만 저장하는 방식임

 

---

 

📊 시간 복잡도 & 공간 복잡도 (Time & Space Complexity)

 

• ⏱️ Time: O(n) — prices 배열을 한 번만 순회
• 💾 Space: O(1) — 추가 메모리 거의 없음

 

---

 

✍️ 회고 (What I Learned)

 

• 변수 이름 하나만 틀려도 NameError 발생
• return의 위치는 루프 바깥에 있어야 전부 순회 가능
• Python에서는 float('inf')를 최대값 비교용 초기값으로 많이 사용함
• 이 문제는 코딩 테스트에서 자주 나오는 기본 탐욕 문제

 

---

 

🔗 마무리 (Closing)

 

이번 문제를 통해 Python의 조건문, 반복문, 그리고 변수 추적 능력을 훈련할 수 있었다