LeetCode

LeetCode 121 Best Time to Buy and Sell Stock 풀이: 최저가를 유지하는 그리디

작성·코드 검증: solve together · 작성 언어: Python

0. 문제 링크와 출처

한 번 매수한 뒤 미래에 한 번 매도해 얻을 수 있는 최대 수익을 찾아야 한다. 현재까지의 최저 가격만 기억하면 각 날짜를 매도일로 판단할 수 있어 구현은 간단하지만, 매수일이 매도일보다 앞서야 한다는 조건을 지켜야 하므로 Level 2로 판단했다.

1. 문제 요약

각 날짜의 주식 가격이 담긴 prices 배열이 주어진다. 서로 다른 두 날짜를 골라 먼저 매수하고 나중에 매도했을 때 얻을 수 있는 최대 수익을 반환한다. 수익을 만들 수 없다면 거래하지 않고 0을 반환한다.

조건은 다음과 같다.

  • 매수일은 매도일보다 앞서야 한다.
  • 주식을 한 번만 매수하고 한 번만 매도할 수 있다.
  • prices[i]는 i번째 날의 가격이다.
  • 가격 배열의 길이는 1 이상 10^5 이하다.
  • 가격은 0 이상 10^4 이하다.

수익은 매도가 - 매수가로 계산한다. 예를 들어 [7, 1, 5, 3, 6, 4]에서는 1에 매수하고 6에 매도하면 최대 수익 5를 얻는다.

2. 문제 해결에 사용되는 알고리즘이나 자료구조 설명

매도일을 고정하면 매수 후보는 하나로 압축된다

날짜 i를 매도일로 고정하면 수익은 prices[i] - prices[j]이고, 매수일 j는 i보다 앞서야 한다. 매도가가 고정된 상태에서는 과거 가격 중 가장 낮은 값만 남기면 최선의 매수가를 놓치지 않는다.

현재 수익 = 현재 가격 - 지금까지의 최저 가격

한 번 순회하면서 다음 두 값을 유지한다.

  • min_price: 현재 날짜 이전까지의 최저 매수가
  • best_profit: 지금까지 계산한 최대 수익

각 날짜를 처리하기 전에는 min_price가 그날보다 앞선 최저가이고, best_profit이 이미 확인한 모든 매수·매도 쌍의 최대 수익이다. 현재 가격으로 먼저 매도 수익을 계산한 다음 최저가를 갱신하면 매수일이 매도일보다 앞선다는 조건이 상태 전이에서 보장된다.

날짜 인덱스 가격 오늘 매도했을 때의 수익 후보 갱신 후 최저가 갱신 후 최대 수익
0 7 거래 전 7 0
1 1 -6 1 0
2 5 4 1 4
3 3 2 1 4
4 6 5 1 5
5 4 3 1 5

가격이 계속 내려가도 거래하지 않는 선택이 허용되므로 best_profit의 초기값 0이 답을 보호한다. 마지막 날짜까지 확인하면 모든 가능한 매도일의 최선 수익을 비교한 셈이다.

오답 접근과 반례

배열 전체의 최댓값과 최솟값만 빼면 순서를 무시하게 된다.

prices = [7, 1, 5]

전체 최댓값 7과 최솟값 1의 차이는 6이지만, 7이 1보다 앞에 있어 1에 매수하고 7에 매도할 수 없다. 실제 최대 수익은 7에 매수하는 거래를 포기하고 1에 매수해 5에 매도하는 4다.

시간·공간 복잡도

가격 배열을 한 번만 순회하므로 시간 복잡도는 O(n)이다. 최저 가격과 최대 수익만 변수로 저장하므로 공간 복잡도는 O(1)이다.

3. 문제 해결 코드 (Python)

class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        min_price = prices[0]
        best_profit = 0

        for price in prices[1:]:
            best_profit = max(best_profit, price - min_price)
            min_price = min(min_price, price)

        return best_profit

현재 가격을 매도 가격으로 먼저 사용하고, 그 다음 최저 매수가를 갱신한다. 가격이 하락하는 날에는 수익이 증가하지 않지만 더 좋은 미래 매수 후보가 되므로 min_price만 바뀐다. 배열 길이가 1인 경우에는 반복문을 실행하지 않고 0을 반환한다.

복사해 실행할 테스트

아래 assert를 풀이 코드와 같은 Python 파일에 붙여 실행하면 공식 예제와 단일 원소 경계를 재현할 수 있다.

solver = Solution()
assert solver.maxProfit([7, 1, 5, 3, 6, 4]) == 5
assert solver.maxProfit([7, 6, 4, 3, 1]) == 0
assert solver.maxProfit([5]) == 0

4. 공식 예제와 추가 검증

작성한 maxProfit 함수를 Python으로 실행해 공식 예제와 경계 사례를 확인했다.

공식 예제

입력 기대 출력 확인 결과
prices = [7,1,5,3,6,4] 5 통과
prices = [7,6,4,3,1] 0 통과

추가 검증 1: 가격이 두 날만 주어진 경우

입력: prices = [1, 2]
기대 출력: 1
확인 결과: 통과
검증 목적: 가장 짧은 유효 거래에서 하루 뒤 매도하는지 확인

추가 검증 2: 가격이 하나뿐인 경우

입력: prices = [5]
기대 출력: 0
확인 결과: 통과
검증 목적: 매수와 매도를 모두 할 수 없는 최소 입력 확인

추가 검증 3: 최저가 뒤에 여러 고점이 있는 경우

입력: prices = [2, 4, 1, 5]
기대 출력: 4
확인 결과: 통과
검증 목적: 중간에 더 낮은 매수가가 갱신된 뒤 최대 수익을 계산하는지 확인

추가 검증 4: 같은 가격만 반복되는 경우

입력: prices = [3, 3, 3]
기대 출력: 0
확인 결과: 통과
검증 목적: 가격 차이가 없는 거래의 경계 처리 확인

5. 다른 풀이 방식 검색 및 비교

모든 매수일과 그 이후의 매도일을 조합하는 완전탐색은 순서를 명확히 확인할 수 있지만 O(n^2) 시간이 필요하다. 투 포인터로 왼쪽을 매수일, 오른쪽을 매도일로 두고 가격이 더 낮아질 때 매수 포인터를 옮기는 방식도 같은 O(n) 결과를 얻는다.

이 글에서는 매도일을 현재 순회 위치로 고정하고 과거 최저가를 갱신하는 방식을 선택했다. 매도일마다 최적 매수가가 왜 최저가인지 수식으로 바로 설명할 수 있고, 별도의 포인터 상태 없이 min_price와 best_profit만 유지하면 되기 때문이다.

마무리

Best Time to Buy and Sell Stock은 미래 가격을 예측하는 문제가 아니라, 현재까지의 최저 매수가와 오늘 매도했을 때의 수익을 비교하는 문제다. 가격을 한 번 순회하며 최저가와 최대 수익을 갱신하면 매수·매도 순서를 지키면서 O(n) 시간과 O(1) 공간으로 해결할 수 있다.

#그리디#LeetCode#난이도 2