122. Best Time to Buy and Sell Stock II

난이도: 중간 (Medium)

링크: LeetCode 122

풀이 날짜: 2025/10/15

 

1. 문제 이해

여러 날 동안의 주식 가격이 주어졌을 때, 여러 번의 거래(사고팔기)를 통해 얻을 수 있는 최대 이익을 구하는 문제다.

단, 동시에 여러 주식을 보유할 수 없고, 하루에 사고 그다음 날 파는 식으로 거래해야 한다.

 

즉, 가격이 오르면 그 차익을 모두 더하고, 가격이 떨어지면 아무 행동도 하지 않는 방식으로 최대 이익을 계산한다.

 

2. 풀이 아이디어

이 문제의 핵심은 “모든 상승 구간의 이익을 더하는 것”이다.

 

가격이 오를 때마다 팔았다가 다시 사는 것이 전체적으로 봤을 때 최대 이익을 보장한다.

만약 가격이 계속 오르는 경우, 예를 들어 [1,2,3,4] 라면, 

• 한 번만 거래하면: 4 - 1 = 3
• 여러 번 거래하면: (2-1) + (3-2) + (4-3) = 3 -> 결과는 동일하다.

하지만 만약 가격이 중간에 떨어졌다가 다시 오르는 경우, 예를 들어 [1, 5, 3, 6]이라면,

• 한 번 거래: 6 - 1 = 5
• 여러 번 거래: (5 - 1) + (6 - 3) = 7 → 더 큰 이익!

모든 상승 구간에서 차익을 합산하면 결과적으로 최적의 해가 된다. 주가가 오를 때마다 파는 행위는 결국 전체 그래프의 오름폭을 모두 더하는 것과 같기 때문이다.

 

3. 풀이코드

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
  let result = 0;

  for (let i = 1; i < prices.length; i++) {
    const gap = prices[i] - prices[i - 1];
    if (gap > 0) result += gap;
  }

  return result;
};

구분	복잡도	설명
시간 복잡도	O(n)	한 번의 순회로 최대 이익 계산
공간 복잡도	O(1)	추가 메모리 거의 없음

 

4. 핵심 정리

• 한 번만 거래하는 경우(문제 121)는 “최저점에 사고 최고점에 판다”를 찾는 문제다.
• 여러 번 거래 가능한 경우(이 문제)는 “모든 오름폭을 더한다”로 단순화된다.
• 여러 번 거래가 가능한 이유는, 하락 구간에서 손실을 피하면서 오르는 구간마다 이익을 실현할 수 있기 때문이다.