Best Time to Buy and Sell Stock

[hsskey]

문제 설명 | Best Time to Buy and Sell Stock

주식 가격이 담긴 배열이 주어질 때, 한 번의 거래로 얻을 수 있는 최대 이익을 구하는 문제

📝 제약조건

• 1 ≤ prices.length ≤ 10^5
• 0 ≤ prices[i] ≤ 10^4
• 주식은 한번만 사고 팔 수 있음
• 미래의 가격으로만 팔 수 있음

💡 예시

• Input: [7,1,5,3,6,4]
  • Output: 5
  • 설명: 1에 사서 6에 팔면 최대 이익 5를 얻을 수 있음

문제 해결 과정

Step 1: 문제 이해하기

• 작은 예시로 직접 최대 이익 계산해보기
  • [7,1,5] → 1에 사서 5에 팔면 이익 4
  • [7,6,4] → 어떻게 사고 팔아도 이익을 낼 수 없음 → 0 반환

Step 2: 접근 방법

• 직관적으로 생각하기
  1. 현재까지의 최소 가격을 기억하면서
  2. 현재 가격에서 최소 가격을 뺀 값(이익)이 최대가 되는 경우를 찾기
• 알고리즘 표 작성

minPrice = prices[0] (첫 가격을 최소값으로 설정)
maxProfit = 0 (최대 이익 초기화)
↓
현재 가격 prices[i] 확인
↓
prices[i]가 minPrice보다 작은지 확인
↓
yes -> minPrice 업데이트
↓
현재 가격 - 최소 가격 계산하여 maxProfit과 비교, 더 크면 업데이트

Step 3: 코드 설계

1. 최소 가격과 최대 이익 변수 초기화
2. 배열 순회하면서:
   • 현재 가격이 최소 가격보다 작으면 최소 가격 업데이트
   • 현재 가격 - 최소 가격으로 이익 계산
   • 계산된 이익이 최대 이익보다 크면 최대 이익 업데이트
3. 최대 이익 반환

Step 4: 코드 구현

var maxProfit = function(prices) {
    let minPrice = prices[0]
    let maxProfit = 0
 
    for(let i = 1; i < prices.length; i++) {
        if(minPrice > prices[i]) {
            minPrice = prices[i]
        } 
        maxProfit = Math.max(maxProfit, prices[i] - minPrice)
    }
    return maxProfit
};

[hsskey]

투포인터를 이용한 풀이

Step 2: 접근 방법

• 직관적으로 생각하기
  1. 두 개의 포인터(left, right)를 사용
  2. left는 구매 시점, right는 판매 시점을 나타냄
  3. right 가격이 left 가격보다 높으면 이익 계산
  4. right 가격이 left 가격보다 낮으면 left를 right로 이동
• 알고리즘 표 작성

left = 0 (판매 가격 인덱스)
right = 1 (판매 가격 인덱스)
maxPrice = 0 (최대 이익)
↓
prices[left] < prices[right] 비교
↓
yes -> 이익 계산 후 maxPrice 업데이트
no -> left = right (더 낮은 구매 가격 발견)
↓
right++ (다음 판매 가격 확인)

Step 3: 코드 설계

1. 구매(left), 판매(right) 포인터와 최대 이익 변수 초기화
2. right 포인터가 배열 끝에 도달할 때까지:
   • 구매 가격이 판매 가격보다 낮으면
     • 이익 계산 후 최대 이익 업데이트
   • 구매 가격이 판매 가격보다 높으면
     • left를 right 위치로 이동
   • right 포인터 증가
3. 최대 이익 반환

Step 4: 코드 구현

var maxProfit = function(prices) {
    let left = 0 // buy
    let right = 1 // sell
    let maxPrice = 0

    while(right < prices.length) {
        if(prices[left] < prices[right]) {
            const price = prices[right] - prices[left]
            maxPrice = Math.max(maxPrice, price)
        } else {
            left = right
        }
        right += 1
    }
    return maxPrice
};

[hsskey]

dp를 이용한 풀이

var maxProfit = function(prices) {
    if (prices.length <= 1) return 0;
    
    let dp = new Array(prices.length).fill(0);
    let minPrice = prices[0];
    
    for (let i = 1; i < prices.length; i++) {
        minPrice = Math.min(minPrice, prices[i]);
        dp[i] = Math.max(dp[i-1], prices[i] - minPrice);
    }
    
    return dp[prices.length - 1];
};