121. Best Time to Buy and Sell Stock

LeetCode 121번 풀이

이 글은 Obsidian에서 마이그레이션되었으며, 그 과정에서 AI의 도움을 받았습니다. 오류나 누락된 내용이 있다면 댓글로 알려주세요!

문제

Best Time to Buy and Sell Stock - LeetCode

풀이 1

코드

function maxProfit(prices: number[]): number {
  const totalDays = prices.length;
  let maxProfit = 0;

  for (let buy = 0; buy < totalDays - 1; buy++) {
    for (let sell = buy + 1; sell < totalDays; sell++) {
      const profit = prices[sell] - prices[buy];
      maxProfit = Math.max(maxProfit, profit);
    }
  }

  return maxProfit;
}

시간 복잡도

• 시간 복잡도: O(n²) - 시간초과로 통과하지 않음

풀이 2

아이디어

가장 큰 이익을 보려면 가장 가격이 낮을 때 사야 한다. 그래서 매일 매일 가격을 보면서

• 지금까지 본 가장 낮은 가격을 갱신하고
• 그 낮은 가격에 사서 오늘 판다면 얼마나 이익이 나올지 계산하고
• 최대 이익을 갱신해주기

이 과정을 반복해주면 굳이 모든 쌍을 확인해 줄 필요가 없다.

코드

// prices 배열로 주어진 날들 중에서 사고 팔았을 때 얻을 수 있는 가장 큰 이익 구하기
function maxProfit(prices: number[]): number {
  let minPrice = Infinity;
  let maxProfit = 0;

  for (const price of prices) {
    minPrice = Math.min(minPrice, price);
    maxProfit = Math.max(maxProfit, price - minPrice);
  }

  return maxProfit;
}

피드백

멋진 코드를 위해 신경쓸 포인트 (피드백받은 것…)

• 숫자 최댓값을 사용해야 하는 경우에는 문제 조건에 맞춰 지정하기보다는 Infinity를 사용하는 것이 좀 더 직관적이고 좋다. 문제 조건이 바뀌더라도 안전하고.
• 인덱스가 굳이 필요 없는 상황이라면 for loop 대신 for...of로 간결하게 표현하기