Leetcode 알고리즘 - Best Time to Buy and Sell Stock (121번)

Best Time to Buy and Sell Stock

☞ 문제링크

입력값으로 주식(Stock)의 가격이 나오게 되고, 가장 큰 수익을 내게 되는 경우의 수익값을 반환해주면 됩니다. 예를 들어, 입력값이 7,1,5,3,6,4 인 경우 가격1에 사서 6에 파는 경우 수익이 가장 크게 나오게 됩니다. 7인 경우는 1의 과거이기 때문에 1 이후에 나온 값 중에서만 팔아야합니다.

문제풀이 (java)

순차적으로 읽어가며 가장 작은 값이 나온 경우 minPrice를 대체하고, minPrice와 현재 시장가의 차로 수익을 계산 합니다. 수익이 이전까지 계산된 수익보다 큰 경우 대체합니다. 만약 minPrice를 따로 구하지 않고 모든 경우를 계산 하게 되면 정답을 구할 수는 있으나 효율성이 크게 떨어지게 됩니다.

public int maxProfit(int[] prices) {
    int answer = 0;
    int length = prices.length;
    int minPrice = Integer.MAX_VALUE;
    for (int i = 0; i < length; i++) {
        if (prices[i] < minPrice) {
            minPrice = prices[i];
        }else {
            int i1 = prices[i] - minPrice;
            if (i1 > answer){
                answer = i1;
            }
        }
    }
    return answer;
}

배운점

• 최소값을 찾는 경우 Integer.MAX_VALUE; 로 초기화 하는 방법을 알게 되었다. (양의 정수의 최대값을 구할 때 보통 0으로 초기화 하는 것처럼 사용한다.)
• 효율성을 높이기 위해서는 차근차근 계산해보고 중복이 되는 경우를 생각해야한다.