leetcode top interview 150 | Best Time to Buy and Sell Stock

 

Question

 

i일마다 변동되는 주식가격을 담은 prices 배열이 주어지고, 주식을 구매한 일자의 다음날부터 판매할 수 있다. 이때 얻을 수 있는 최대 수익을 반환한다. 

 

 

Not accepted code

class Solution {
    public int maxProfit(int[] prices) {
        int max=0;
        for(int i=0; i<prices.length-1; i++){
            for(int j=i+1; j<prices.length; j++){
                int profit = prices[j] - prices[i];
                if(profit > max) {
                    max = profit;
                }
            }
        }
        return max;
    }
}

 

모든 경우의 수를 탐색하는 코드로 시간복잡도가 O(n^2)에 도달한다. prices의 최대 길이가 10^5이기 때문에 시간초과가 발생했다.

 

 

Accepted Code

class Solution {
    public int maxProfit(int[] prices) {
        int minPrice = prices[0];
        int maxProfit = 0;
        for(int i=1; i<prices.length; i++){
            if(minPrice > prices[i]) minPrice = prices[i];
            int profit = prices[i] - minPrice;
            if(profit > maxProfit) maxProfit = profit;
        }
        return maxProfit;
    }
}

 

solve

 

수익 = 판매한 가격 - 구매한 가격

수익이 최대화 되려면 판매한 가격과 구매한 가격의 차이가 커야한다. 따라서 판매가격은 크고 구매가격은 작아야한다. 그리고 구매한 다음에 판매할 수 있기 때문에 판매한 가격의 index는 구매한 가격의 index보다 항상 크다.

 

이중 포문으로 모든 경우의 수를 탐색하지 않아도 되는게, 중간에 이전의 구매가격보다 더 작은 가격이 발생하면 갱신해주고 해당 값으로 수익계산을 해주면 된다. 따라서 minPrice 변수를 선언하여 적은 가격 발견 시 반복문 안에서 구매가격을 갱신해주고 수익을 비교해 maxProfit에 갱신해줬다. 이로써 O(n)만에 최대수익 가격을 리턴할 수 있었다.

 

 

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description/?envType=study-plan-v2&envId=top-interview-150 

Best Time to Buy and Sell Stock - LeetCode