[Leetcode Top Interview 150] 121. Best Time to Buy and Sell Stock

난이도 : easy

문제링크

• prices라는 정수형 배열이 주어진다
• prices의 요소는 인덱스 i날짜의 재고 가격을 뜻한다
• 이익이 최대가 되는 날짜를 구하라

 

1. 접근법

• 가장 싸게사서 가장 비싸게 팔아야 최대의 이익이 발생함
• 내림차순일 경우, 0을 리턴함
• 판매일은 구매일 이후여야 한다
• 구매가 - 판매가가 최대 이익값

 

2. 의사코드

for (int i = 1; i < prices.length; i++) {
    if (prev < prices[i] && isDesc) {
        // 이전 값이 현재 값보다 작다면 내림차순 아님
        isDesc = false;
    }

    prev = prices[i];

    if (min > prices[i] && i < maxDay) { // buy
        // min 값 업데이트
        // minday는 현재 인덱스
    }

    if (max < prices[i] && i > minDay) { // sell
        // max 값 업데이트
        // maxday는 현재 인덱스
    }
}

return isDesc ? 0 : max-min;

 

3. 구현 코드

public int maxProfit(int[] prices) {
    int min = prices[0], max = 0, minDay = 0, maxDay = prices.length-1, prev = prices[0];
    boolean isDesc = true;

    for (int i = 1; i < prices.length; i++) {
        if (prev < prices[i] && isDesc) {
            isDesc = false;
        }

        prev = prices[i];

        if (min > prices[i] && i < maxDay) { // buy
            min = prices[i];
            minDay = i;
        }

        if (max < prices[i] && i > minDay) { // sell
            max = prices[i];
            maxDay = i;
        }
    }

    return isDesc ? 0 : max-min;
}

 

4. 시간복잡도, 공간복잡도 예상

• 시간복잡도 : O(n) - 모든 데이터를 순회함
• 공간복잡도 : O(1) - 상수 데이터만 메모리에 할당됨

 

5. 개선점

• 구현 실패
  • [2,1,2,1,0,1,2] 테스트케이스에서 실패

 

6. 회고

• 도저히 생각이 안나 풀이를 찾아보았다

public int maxProfit(int[] prices) {
    int min_val = Integer.MAX_VALUE;
    int max_profit = 0;

    for (int i = 0; i <prices.length; i++) {
        if (prices[i] < min_val) {
            min_val = prices[i];
        } else if (prices[i] - min_val > max_profit) {
            max_profit = prices[i] - min_val;
        }
    }

    return max_profit;
}

(출처 : NickWhite)

• 한 분기 내에서 가장 작은값과 가장 큰 이익을 업데이트한다
  • 구매 비용
    • 가장 작은 값으로 할 수 있음
  • 판매 비용
    • 최소 구매비용의 이후 날짜로 판매할 수 있음
    • 가장 큰 판매가로 판매할 수 있음