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

문제 파악

 

i날 주식 가격은 prices[i] 과 같이 배열 형태로 주어진다.

 

최대로 수익을 반환해야한다.

 

만약, 어떠한 수익도 얻지 못한다면 0 을 반환한다.

 

---

풀이

 

1️⃣ 이중 for문 풀이 - 시간 초과

 

가장 먼저 떠오른 풀이는, 파는 날을 고정하고

 

파는 날 이전의 가격들을 순회하면서 최댓값을 구해야겠다고 생각했다.

 

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

        return ans;
    }
}

 

결과

하지만, 이 방식은 시간 복잡도가 O(N^2) 으로 시간 초과가 발생했다.

 

시간 복잡도가 O(N) 이 될 수 있는 풀이를 다시 생각해보았다.

 

2️⃣ O(N) 풀이

먼저 특정 구역에서 가장 낮은 값을 구할 수 있는 로직을 생각해봤다.

 

가장 싸게 사야 이익을 최대화 할 수 있기 때문이다.

 

        int buy = prices[0];

        for(int i=1;i<prices.length;i++){
            if(prices[i]<buy){
                buy = prices[i];
            }
        }

 

위와 같은 코드로 작성하면, 0~i번째 원소 중에서 가장 작은 값이 buy에 입력된다.

 

만약, 비교하는 가격( prices[i] ) 이 buy보다 큰 경우는 판매를 할 수 있고

 

이익을 계산해서 최댓값이면 갱신해주는 작업을 해주면 된다.

 

class Solution {
    public int maxProfit(int[] prices) {
        int ans = 0;
        int buy = prices[0];

        for (int i = 1; i < prices.length; i++) {
            if (prices[i] < buy) {
                buy = prices[i];
            } else {
                ans = Math.max(ans, prices[i] - buy);
            }

        }
        return ans;
    }
}

 

결과

---

📖 회고

 

사실 이중 for문 방식으로 통과할 정도로 연산 시간이 널널한 문제는 거의 없다..ㅎ

 

이중 for문 방식이 먼저 떠올랐다면, 더 좋은 방법이 없는지 고민해보는 습관을 가져야겠다.