121. Best Time to Buy and Sell Stock

난이도: 쉬움 (Easy)

링크: LeetCode 121

풀이 날짜: 2025/10/15

 

1. 문제 이해

주식 가격 배열 prices가 주어질 때, 한 번의 매수와 매도로 얻을 수 있는 최대 이익을 구하는 문제이다.

• 매수는 반드시 매도보다 먼저 해야 함.
• 매도는 한 번만 가능.

 

 

2. 접근 아이디어

한 번의 거래로 최대 수익을 내야 하므로, 

1. 최소 가격을 추적 - 현재까지 본 가격 중 가장 작은 값을 기록 → minPrice
2. 현재 가격으로 가능한 최대 이익 계산 - prices[i] - minPrice → 지금 팔면 얻을 수 있는 최대 이익
3. 최대 이익 갱신 - maxProfit = Math.max(maxProfit, prices[i] - minPrice)
4. 최소 가격 갱신 - minPrice = Math.min(minPrice, prices[i])

즉, 배열을 한 번만 순회하면서 현재까지의 최적 매수와 최대 이익을 동시에 관리하는 방식이다.

 

3. 풀이코드

var maxProfit = function(prices) {
  let maxProfit = 0;
  let minPrice = prices[0];

  for(let i=1; i<prices.length; i++) {
    // 현재 가격으로 얻을 수 있는 최대 이익
    maxProfit = Math.max(maxProfit, prices[i] - minPrice);
    // 최소 가격 갱신
    minPrice = Math.min(minPrice, prices[i]);
  }  

  return maxProfit;
};

• 시간 복잡도: O(n) — 배열 한 번 순회
• 공간 복잡도: O(1) — 추가 배열 없이 변수만 사용

 

4. 핵심 포인트

• 배열을 순회하며 최소 가격과 최대 이익을 동시에 갱신한다.
• 한 번만 순회하므로 효율적이다. 시간복잡도 O(n).
• 매수-매도 시점 조건을 변수 관리로 자연스럽게 처리한다.