문제 개요
시간 순서대로 나열된 어떤 회사의 주가 리스트가 있다고 가정해 봅시다. 이때 딱 한 번 주식을 사고팔아 얻을 수 있는 최대 이익을 구해야 합니다. 단, 반드시 먼저 매수한 후에 매도해야 한다는 조건이 있습니다.
예를 들어 입력이 다음과 같다면,
prices = [10, 12, 9, 6, 8, 12]
출력은 6이 됩니다. 6원일 때 매수하고 12원일 때 매도하면 이익은 12 − 6 = 6이 되기 때문입니다.
해결 접근 방법
이 문제는 배열을 한 번만 순회하면서 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 지금까지 확인한 주가 중 최솟값(min_stock)을 계속 추적합니다.
- 현재 가격에서 최솟값을 뺀 값, 즉 현재 시점에 팔았을 때의 이익을 계산합니다.
- 그 이익이 기록된 최대 이익(max_profit)보다 크면 갱신합니다.
알고리즘 단계
- max_profit := 0 으로 초기화
- min_stock := 무한대(infinity)로 초기화
- prices의 각 price에 대해:
- max_profit := max_profit과 (price − min_stock) 중 더 큰 값
- min_stock := min_stock과 price 중 더 작은 값
- max_profit 반환
이 방식은 모든 가능한 매수·매도 조합을 비교하지 않고도 최적의 답을 찾을 수 있으며, 시간 복잡도는 O(n), 공간 복잡도는 O(1)로 매우 효율적입니다.
파이썬 구현 예제
아래 코드를 통해 더 잘 이해해 보겠습니다.
class Solution:
def solve(self, prices):
max_profit = 0
min_stock = float('inf')
for price in prices:
max_profit = max(max_profit, price - min_stock)
min_stock = min(min_stock, price)
return max_profit
ob = Solution()
print(ob.solve([10, 12, 9, 6, 8, 12]))입력
[10, 12, 9, 6, 8, 12]
출력
6
동작 원리 살펴보기
위 예제에서 알고리즘이 진행되는 과정을 단계별로 보면 다음과 같습니다.
- 10 → min_stock = 10, max_profit = 0
- 12 → 이익 12−10=2, max_profit = 2
- 9 → min_stock = 9, max_profit = 2 유지
- 6 → min_stock = 6, max_profit = 2 유지
- 8 → 이익 8−6=2, max_profit = 2 유지
- 12 → 이익 12−6=6, max_profit = 6
최종적으로 최대 이익 6이 반환됩니다. 만약 주가가 계속 하락만 한다면 매도할 기회가 없으므로 함수는 0을 반환하게 됩니다.