LeetCode 121 - Best Time to Buy and Sell Stock

문제 설명

주어진 prices 배열에서, i번째 날에 주식을 사고 j번째 날에 판다고 할 때 (i < j), 얻을 수 있는 최대 이익을 구하는 문제입니다. 주식은 한 번만 사고 한 번만 파는 것만 가능합니다.

접근 방법 - Greedy (그리디) 방식

이 문제를 가장 효율적으로 해결하는 방법은 앞에서부터 최소 가격을 저장하면서 현재 가격과의 차이로 최대 이익을 계산하는 것입니다.

핵심 아이디어

• 한 번 순회하면서 최소 가격(minPrice) 을 지속적으로 업데이트합니다.
• 현재 가격에서 최소 가격을 뺀 값을 현재까지의 최대 이익(maxProfit) 으로 관리합니다.
• 과거 가격만 보고, 미래 가격에 팔기 위해 앞에서부터 탐색합니다.

코드

function maxProfit(prices: number[]): number {
  let minPrice = Number.MAX_SAFE_INTEGER
  let maxProfit = 0

  for (let price of prices) {
    if (price < minPrice) {
      minPrice = price
    } else {
      maxProfit = Math.max(maxProfit, price - minPrice)
    }
  }

  return maxProfit
}

시간 및 공간 복잡도

구분	복잡도
시간 복잡도	O(n)
공간 복잡도	O(1)

• 한 번의 for문으로 전체 배열을 순회 → O(n)
• 추가 배열이나 자료구조 없이 변수만 사용 → O(1)

주요 포인트

• 앞에서부터 탐색하여 최소 가격을 찾고, 현재 가격과의 차이로 최대 이익 계산
• 시간 효율성과 공간 효율성이 모두 최적
• 인터뷰에서도 자주 출제되는 전형적인 최적화 문제 패턴

예시

Input: prices = [7,1,5,3,6,4]
Output: 5

설명:
- 최소 가격 = 1 (2번째 날)
- 최대 이익 = 6 - 1 = 5 (5번째 날에 팔았을 때)