𝗟𝗲𝗲𝘁𝗰𝗼𝗱𝗲 𝟭𝟱𝟬 | 𝗗𝗮𝘆 𝟱: 주식 매수 및 매도 최적 시점

Leetcode 121은 주식을 매수하고 매도하기에 가장 좋은 시점을 찾는 문제입니다. 가격 배열이 주어지며, 각 인덱스는 날짜를, 값은 해당 날짜의 가격을 나타냅니다.

목표는 간단합니다. 어느 한 날에 매수하여 미래의 어느 날에 매도함으로써 최대 이익을 얻는 것입니다. 만약 이익을 낼 수 없다면 0을 반환합니다.

문제 제약 조건:

  • 배열 길이 최대 100,000.
  • 가격 최대 10,000.
  • 반드시 구매한 후에 판매해야 합니다.

접근 방식 1: 단순한 방법 (Brute Force)

브루트 포스 방식은 모든 가능한 매수 및 매도 쌍을 일일이 확인합니다. 이 방식은 두 개의 루프를 사용합니다.

  • 시간 복잡도: O(n²)
  • 문제점: 너무 느립니다.

만약 1,000일의 데이터가 있다면 1,000,000번의 확인을 수행해야 합니다. 100,000일이라면 10,000,000,000번의 확인을 수행해야 합니다. 이는 Leetcode에서 시간 초과(timeout)를 발생시킵니다.

접근 방식 2: 최적화된 방법 (One Pass)

minPrice와 maxProfit이라는 두 개의 변수를 사용하여 단 한 번의 순회(one pass)로 문제를 해결할 수 있습니다.

  • 시간 복잡도: O(n)
  • 공간 복잡도: O(1)

작동 방식:

  1. minPrice를 Infinity로 설정합니다.
  2. maxProfit을 0으로 설정합니다.
  3. 각 가격을 순회합니다.
  4. 현재 가격이 minPrice보다 낮으면, minPrice를 업데이트합니다.
  5. 현재 가격에서 minPrice를 뺀 값이 maxProfit보다 크면, maxProfit을 업데이트합니다.

가격 [7, 1, 5, 3, 6, 4]에 대한 예시 추적:

  • 1일차: 가격 7. minPrice는 7이 됩니다. maxProfit은 0으로 유지됩니다.
  • 2일차: 가격 1. minPrice는 1이 됩니다. maxProfit은 0으로 유지됩니다.
  • 3일차: 가격 5. 5 - 1 = 4. maxProfit은 4가 됩니다.
  • 4일차: 가격 3. 3 - 1 = 2. maxProfit은 4로 유지됩니다.
  • 5일차: 가격 6. 6 - 1 = 5. maxProfit은 5가 됩니다.
  • 6일차: 가격 4. 4 - 1 = 3. maxProfit은 5로 유지됩니다.

최종 정답: 5.

최적화된 버전은 각 가격을 단 한 번씩만 확인하기 때문에 훨씬 효율적입니다. 대규모 데이터셋에서도 성능이 잘 유지됩니다.

Source: https://dev.to/afuji/leetcode-150-day-5-best-time-to-buy-and-sell-stock-naive-vs-optimized-4mk1