Best Time to Buy and Sell Stock

문제

어떤 주식의 매일의 가격을 나타내는 배열 prices가 주어집니다. prices[i]는 i번째 날의 주식 가격입니다. 주식을 단 한 번 사고 단 한 번 팔아서 얻을 수 있는 최대 이익을 구하는 프로그램을 작성하는 문제입니다. 만약 어떤 이익도 얻을 수 없다면 0을 반환해야 합니다.

• 입력: 주식 가격을 담은 정수 배열 prices (길이 1 이상 100,000 이하, 각 가격은 0 이상 10,000 이하)
• 출력: 얻을 수 있는 최대 이익 (이익이 없으면 0 반환)

링크: https://leetcode.com/problems/best-time-to-buy-and-sell-stock

풀이: 저점 매수 및 고점 매도 (O(N) 탐색)

이중 반복문을 사용하여 모든 매수/매도 타이밍을 검사하면 시간 복잡도가 O(N^2)이 되어 시간 초과가 발생할 수 있습니다. 이를 최적화하기 위해, 배열을 단 한 번 순회(O(N))하면서 '지금까지 본 가장 싼 가격(저점)'을 기억해두고, '오늘 가격에서 저점을 뺀 이익'을 매번 계산하여 최댓값을 갱신하는 방식입니다.

• 최소 가격 초기화: 지금까지 탐색한 주식 가격 중 가장 작은 값을 저장할 변수 min을 선언합니다. LeetCode 문제의 조건에서 주식 가격은 최대 10,000이므로, 초기값을 10,000(또는 그 이상)으로 설정하여 첫 번째 가격이 자연스럽게 최솟값으로 갱신되도록 합니다.
• 배열 순회 및 갱신:
  • 배열을 순회하며 매일의 가격(price)을 확인합니다.
  • 최대 이익 갱신: 현재 가격에서 지금까지의 최소 가격을 뺀 값(price - min)이 기존의 최대 이익(ans)보다 크다면 최대 이익을 갱신합니다.
  • 최소 가격 갱신: 현재 가격이 지금까지의 최소 가격(min)보다 작다면 최소 가격을 갱신합니다.
• 순서 보장: 이익을 먼저 계산하고 최소 가격을 갱신하므로, '미래에 사서 과거에 파는' 논리적 오류가 원천적으로 차단됩니다. 매도는 항상 매수 이후에 이루어집니다.

코드

import java.util.*;

class Solution {
    public int maxProfit(int[] prices) {
        int ans = 0; // 최대 이익 초기화 (이익이 없으면 0)

        // 문제의 제한사항(가격 최대 10,000)을 고려한 초깃값 설정
        int min = 10000; 
        
        for (int price : prices) {
            // 1. 현재 가격에 팔았을 때의 이익을 계산하여 최댓값 갱신
            ans = Math.max(ans, price - min);
            
            // 2. 지금까지의 가장 낮은 매수 가격 갱신
            min = Math.min(min, price);
        }

        return ans;
    }
}

알고리즘 분류

배열 (Array), 다이나믹 프로그래밍 (Dynamic Programming), 탐욕법 (Greedy)