[LeetCode] 121. Best Time to Buy and Sell Stock

Best Time to Buy and Sell Stock - LeetCode

 

날짜별 주식가격이 주어지고 주식가격을 특정일에 사서 특정일에 판다고 가정했을때

가장 큰 수익을 냈을경우 그 수익을 구하는 문제입니다.

 

수익을 내지 못할경우 0을 반환합니다.

 

문제 접근

단순 반복을 해서 구하면 될거라고 생각했습니다.

 

2중 반복문을 통해 날짜A를 기준으로 A의 다음날짜들을 탐색하는 방법입니다.

public int maxProfit(int[] prices) {
        int ret = 0;

        for (int i = 0; i < prices.length-1; i++) {
            for (int j = i+1; j < prices.length; j++) {
                if (prices[i] > prices[j]) {
                    break;
                } else {
                    ret = Math.max(ret, prices[j] - prices[i]);
                }
            }
        }
        return ret;
    }

시간복잡도

당연히 시간초과가 났습니다.

그 이유는 prices의 길이가 10의 5승이기 때문입니다.

 

O(n2)의 시간복잡도를 갖고있는 제 코드는 효율성면에서 많이 부족합니다.

 

 

다른사람의 풀이

시간복잡도를 O(n)으로 줄인 코드입니다.

최소값을 기억할 변수를 선언하여 탐색할때마다 최소값을 저장합니다.

저장된 최소값과 지금 바라보는 요소의 차를 구해서 Math.max함수를 사용해 ret변수에 담아줍니다.

 

위 과정을 매번탐색동안 거쳐 최대수익을 구할 수 있습니다.

 

    public int maxProfit(int[] prices) {
        int ret = 0;
        int min = (int) 1e9;

        for (int i = 0; i < prices.length; i++) {
            min = Math.min(min, prices[i]);
            ret = Math.max(ret, prices[i] - min);
        }
        return ret;
    }

 

 

느낀점

문제풀이법이 떠오르지 않을때에는 그림으로 그래프를 그려가며 이해하면 수월하게 풀리는것 같습니다.

문제를 이해하기위해 적극적으로 노력해야겠습니다.

 

참고

도서 : 파이썬 알고리즘 인터뷰