View in English →

Code › algorithm-study

LeetCode 121 - Best Time to Buy and Sell Stock

이전 날짜의 최저 가격을 갱신하며 최대 수익을 구하는 one-pass Python 풀이

algorithmleetcodearraygreedyone-passpythonlearning

오늘 문제는 주식이다! ㅋㅋ 날짜별로 주식 가격이 주어졌을 때, 한 번 사고 한 번 팔아서 얻을 수 있는 최대 수익을 구하는 Easy 문제다. Brute force로는 쉽게 풀리는데, 아래에서 푼 방법은 나는 쉽게 떠올리지 못했다.

문제 링크 & 설명

  • 문제 링크: 121. Best Time to Buy and Sell Stock
  • 요약: prices의 각 원소가 날짜별 주식 가격을 나타낼 때, 먼저 매수하고 이후 날짜에 매도해서 얻을 수 있는 최대 수익을 반환한다. 수익을 낼 수 없다면 0을 반환한다.

prices가 [7, 1, 5, 3, 6, 4]라면 가격이 1일 때 사고 6일 때 팔아 최대 수익 5를 얻는다. 중요한 조건은 매수일이 매도일보다 앞에 있어야 한다는 점이다.

접근 방법

어떤 날짜의 가격을 매도가로 정했을 때 얻을 수 있는 최대 수익은 그 이전까지의 가장 낮은 가격에 샀을 때 나온다. 따라서 배열을 왼쪽부터 한 번 순회하면서 다음 두 값만 관리하면 된다.

  • min_price는 현재까지 확인한 최저 가격이다.
  • max_profit은 현재까지 계산한 최대 수익이다.

현재 price에서 min_price를 빼면 오늘 매도했을 때의 수익이 나온다. 이 값을 max_profit과 비교한 뒤, 현재 가격이 더 낮다면 이후 날짜의 매수를 위해 min_price를 갱신한다.

for price in prices:
    max_profit = max(max_profit, price - min_price)
    min_price = min(min_price, price)

[7, 1, 5, 3, 6, 4]를 순회하면 min_price는 7에서 시작해 두 번째 값 1에서 갱신된다. 이후 가격 5에서는 수익 4, 가격 3에서는 수익 2, 가격 6에서는 수익 5를 계산하며 max_profit이 최종적으로 5가 된다.

트러블 슈팅

처음에는 가격과 원래 인덱스를 튜플로 묶은 뒤 가격을 기준으로 정렬하는 방법을 생각했다. 가장 싼 가격에는 왼쪽 포인터를, 가장 비싼 가격에는 오른쪽 포인터를 두고 양 끝에서 좁혀오면서 매수 인덱스가 매도 인덱스보다 작을 때 수익을 계산하려고 했다.

그런데 인덱스 조건을 만족하지 않았을 때 어느 포인터를 옮겨야 할지 기준을 생각하는데 잘 안떠올랐다. 예를 들어 prices가 [3, 2, 6, 1, 4]라면 가격과 인덱스를 정렬한 결과는 다음과 같다.

[(1, 3), (2, 1), (3, 0), (4, 4), (6, 2)]

양 끝의 가격 1과 6은 매수 인덱스 3이 매도 인덱스 2보다 크기 때문에 거래할 수 없다. 여기서 오른쪽 포인터를 옮기면 1에 사서 4에 파는 수익 3을 찾지만, 실제 최대 수익은 인덱스 1에서 2에 사고 인덱스 2에서 6에 파는 4다. 이 예시에서는 왼쪽 포인터를 옮겨야 하지만, 다른 배열에서는 오른쪽 포인터를 옮겨야 할 수 있다.

정렬된 가격만으로는 한쪽 후보를 버려도 최적해가 남는다는 보장이 없어서 일반적인 투 포인터 방식으로 탐색 범위를 줄일 수 없었다. 양쪽 경우를 모두 확인하면 조합을 다시 탐색해야 하고, 가격 정렬에도 O(n log n)이 필요하므로 이 접근은 사용하지 않았다.

왼쪽부터 순회하며 현재까지의 min_price만 사용하면 이 조건이 지켜진다. 현재 price로 수익을 먼저 계산하고 그다음 min_price를 갱신하므로, 새로 발견한 최저 가격은 이후 날짜의 매수 가격으로 사용된다. 첫 번째 반복에서는 첫날의 가격을 같은 값과 비교해 수익 0을 계산한다.

max_profit을 0으로 시작하는 것도 같은 이유인데, 가격이 계속 하락하면 모든 price - min_price가 0 이하이므로 거래하지 않았을 때의 수익인 0을 그대로 반환한다.

복잡도 분석

  • 시간 복잡도: O(n)
    • prices를 왼쪽부터 한 번 순회한다. n은 prices의 길이다.
  • 공간 복잡도: O(1)
    • 배열 크기와 관계없이 min_price와 max_profit만 저장한다.

구현 코드

from typing import List

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

        for price in prices:
            max_profit = max(max_profit, price - min_price)
            min_price = min(min_price, price)

        return max_profit

요약 및 회고

Easy이지만 최저가를 계속 저장해야한다는 인사이트를 못 떠올리면 최적화된 풀이로 풀기가 힘들 수 있는 문제이다. 그래서 여러 방면으로 생각 해 보는게 좋다는 것을 느꼈다.