LeetCode 122 - Best Time to Buy and Sell Stock 2

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii

 

•  입력
  • int [] prices i 일의 가격이 들어있는 배열
• 출력
  • 여러 번 사고팔 수 있을 때의 최대 이익
  • 단 한 번에 하나의 주식만 보유할 수 있다.

구매와 판매를 여러 번 할 수 있는 상황이다. 대신 주식은 한 번에 한 개만 보유할 수 있다.

이익이 나는 동안은 가지고 있다가 가격이 내려가기 직전에 판매해야 최대 이익을 볼 수 있다.

이는 곧 이전의 기록과 비교하는 동작이다.

Deque를 이용한 풀이

가장 최근 기록과 비교하는 것은 stack을 사용하면 될 것 같다.

그런데 이익을 계산할 때 가장 아래에 쌓여 있는 데이터와 가장 위에 쌓여 있는 데이터의 차이를 계산해야 한다.

차라리 그럴거면 deque를 사용해 양 쪽 접근이 쉽게 처리하겠다.

class Solution {
    public int maxProfit(int[] prices) {
        int profit = 0;
        
        Deque<Integer> deque = new ArrayDeque<>();
        deque.addLast(prices[0]);

        for (int i = 1; i < prices.length; i++) {
            if (deque.peekLast() > prices[i]) {
                int max = deque.peekLast();
                int min = deque.peekFirst();

                profit += max - min;

                while (!deque.isEmpty()) {
                    deque.poll();
                }
            }
            deque.addLast(prices[i]);              
        }

        if (!deque.isEmpty()) {
            int max = deque.peekLast();
            int min = deque.peekFirst();

            profit += max - min;
        }

        return profit;
    }
}

deque에 데이터를 넣는다.

만약 가격이 peekLast보다 작다는 것은 가격이 떨어지는 순간이니 먼저 팔아야 한다.

쌓여있는 가격들에서 가장 위의 가격에서 가장 아래 가격을 뺀 것이 이익이 된다.

만약 데이터가 1개만 들어있다 해도 어차피 이익이 0으로 계산되니 문제없다.

그 후 deque를 비워준 뒤 새로운 가격을 넣어주면 된다.

마지막으로 순회가 끝났을 때 즉 마지막날에 판매가 됐을 때 이익이 발생하는 경우를 고려해줘야 하기 때문에 deque가 비어있지 않다면 이익 계산을 한 번 더 수행해 준 뒤 최종 이익을 반환해 준다.

그리디 알고리즘

하지만 위의 방식은 쓸데없는 공간을 사용하고 복잡도를 증가시키고 있다.

이 문제는 그냥 그리디 알고리즘으로 가격이 상승하는 구간마다 이익을 취하면 된다.

팔자마자 다시 살 수 있다는 점 때문에 굳이 구간 이익이 최대일 때 팔 필요가 없다.

1. 배열을 한 번 순회한다.
2. 현재 가격이 이전 가격보다 높다면 그 차이를 이익에 더한다.

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

        for (int day = 1; day < prices.length; day++) {
            if (prices[day - 1] < prices[day]) {
                profit += prices[day] - prices[day - 1];
            }
        }

        return profit;
    }
}